Options
Linear kernels and linear-time algorithms for finding large cuts
Citation Link: https://doi.org/10.15480/882.2617
Publikationstyp
Conference Paper
Date Issued
2016-12-01
Sprache
English
Author(s)
TORE-DOI
TORE-URI
First published in
Number in series
64
Start Page
1
End Page
13
Article Number
31
Citation
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Contribution to Conference
Publisher DOI
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
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-Erdös Bound can be implemented in such a way that it runs in linear time 8k · O(m); this significantly improves the previous analysis with run time 8k · O(n4).
We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdös Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. [COCOON 2013].
We improve all known kernels for strongly λ-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k3) vertices to O(k) vertices.
As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in time 2O(k) · nO(1); this answers an open question by Crowston et al. [FSTTCS 2012].
All presented kernels can be computed in time O(km).
We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdös Bound can be implemented in such a way that it runs in linear time 8k · O(m); this significantly improves the previous analysis with run time 8k · O(n4).
We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdös Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. [COCOON 2013].
We improve all known kernels for strongly λ-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k3) vertices to O(k) vertices.
As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in time 2O(k) · nO(1); this answers an open question by Crowston et al. [FSTTCS 2012].
All presented kernels can be computed in time O(km).
Subjects
Fixed-parameter tractability
Kernelization
Max-Cut
DDC Class
004: Informatik
More Funding Information
Supported by ERC Starting Grant 306465 (BeyondWorstCase).
Loading...
Name
LIPIcs-ISAAC-2016-31-1.pdf
Size
551.46 KB
Format
Adobe PDF