1 Search Results for "Etscheid, Michael"

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.31

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

Authors: Michael Etscheid and Matthias Mnich

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: * We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdos Bound can be implemented in such a way that it runs in linear time 8^k · O(m); this significantly improves the previous analysis with run time 8^k · O(n^4). * We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdos Bound with O(k) vertices, improving a kernel with O(k^3) vertices by Crowston et al. [COCOON 2013]. * We improve all known kernels for strongly lambda-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k^3) vertices to O(k) vertices. * As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time 2^{O(k)} * n^{O(1)} ; this answers an open question by Crowston et al. [FSTTCS 2012]. All presented kernels can be computed in time O(km).

Cite as

Michael Etscheid and Matthias Mnich. Linear Kernels and Linear-Time Algorithms for Finding Large Cuts. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{etscheid_et_al:LIPIcs.ISAAC.2016.31,
  author =	{Etscheid, Michael and Mnich, Matthias},
  title =	{{Linear Kernels and Linear-Time Algorithms for Finding Large Cuts}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{31:1--31:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.31},
  URN =		{urn:nbn:de:0030-drops-68016},
  doi =		{10.4230/LIPIcs.ISAAC.2016.31},
  annote =	{Keywords: Max-Cut, fixed-parameter tractability, kernelization}
}

Refine by Author
1 Etscheid, Michael
1 Mnich, Matthias

Refine by Classification

Refine by Keyword
1 Max-Cut
1 fixed-parameter tractability
1 kernelization

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Etscheid, Michael"

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

Abstract

Cite as

Thanks for your feedback!

Could not send message