Designing FPT algorithms for cut problems using randomized contractions

Research output: Contribution to journalArticlepeer-review

Standard

Designing FPT algorithms for cut problems using randomized contractions. / Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, Mohammadtaghi; Pilipczuk, Marcin; Pilipczuk, Michalø.

In: SIAM Journal on Computing, Vol. 45, No. 4, 06.07.2016, p. 1171-1229.

Research output: Contribution to journalArticlepeer-review

Harvard

Chitnis, R, Cygan, M, Hajiaghayi, M, Pilipczuk, M & Pilipczuk, M 2016, 'Designing FPT algorithms for cut problems using randomized contractions', SIAM Journal on Computing, vol. 45, no. 4, pp. 1171-1229. https://doi.org/10.1137/15M1032077

APA

Vancouver

Author

Chitnis, Rajesh ; Cygan, Marek ; Hajiaghayi, Mohammadtaghi ; Pilipczuk, Marcin ; Pilipczuk, Michalø. / Designing FPT algorithms for cut problems using randomized contractions. In: SIAM Journal on Computing. 2016 ; Vol. 45, No. 4. pp. 1171-1229.

Bibtex

@article{aa71f187e8f4414c855a73bbf16b85be,
title = "Designing FPT algorithms for cut problems using randomized contractions",
abstract = "We introduce a new technique for designing xed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the rst xed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2O(k2 log |Σ|)n4 log n deterministic time (even in the stronger, vertex-deletion variant), where k is the number of unsatisfied edges and |Σ| is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satis ed is upper bounded by O(log n) to optimality, which improves over the trivial O(1) upper bound. We prove that the Steiner Cut problem can be solved in 2O(k2 log k)n4 log n deterministic time and O(2O(k2 log k)n2) randomized time, where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering \cut{"} and \uncut{"} constraints at the same time. More precisely, we de ne a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in 2O(k2 log k)n4 log n deterministic time, where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.",
keywords = "fixed-parameter tractability, graph separations problems, randomized contractions, unique label cover",
author = "Rajesh Chitnis and Marek Cygan and Mohammadtaghi Hajiaghayi and Marcin Pilipczuk and Michal{\o} Pilipczuk",
year = "2016",
month = jul,
day = "6",
doi = "10.1137/15M1032077",
language = "English",
volume = "45",
pages = "1171--1229",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics",
number = "4",

}

RIS

TY - JOUR

T1 - Designing FPT algorithms for cut problems using randomized contractions

AU - Chitnis, Rajesh

AU - Cygan, Marek

AU - Hajiaghayi, Mohammadtaghi

AU - Pilipczuk, Marcin

AU - Pilipczuk, Michalø

PY - 2016/7/6

Y1 - 2016/7/6

N2 - We introduce a new technique for designing xed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the rst xed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2O(k2 log |Σ|)n4 log n deterministic time (even in the stronger, vertex-deletion variant), where k is the number of unsatisfied edges and |Σ| is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satis ed is upper bounded by O(log n) to optimality, which improves over the trivial O(1) upper bound. We prove that the Steiner Cut problem can be solved in 2O(k2 log k)n4 log n deterministic time and O(2O(k2 log k)n2) randomized time, where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering \cut" and \uncut" constraints at the same time. More precisely, we de ne a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in 2O(k2 log k)n4 log n deterministic time, where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

AB - We introduce a new technique for designing xed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the rst xed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in 2O(k2 log |Σ|)n4 log n deterministic time (even in the stronger, vertex-deletion variant), where k is the number of unsatisfied edges and |Σ| is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satis ed is upper bounded by O(log n) to optimality, which improves over the trivial O(1) upper bound. We prove that the Steiner Cut problem can be solved in 2O(k2 log k)n4 log n deterministic time and O(2O(k2 log k)n2) randomized time, where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering \cut" and \uncut" constraints at the same time. More precisely, we de ne a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in 2O(k2 log k)n4 log n deterministic time, where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

KW - fixed-parameter tractability

KW - graph separations problems

KW - randomized contractions

KW - unique label cover

UR - http://www.scopus.com/inward/record.url?scp=84991010767&partnerID=8YFLogxK

U2 - 10.1137/15M1032077

DO - 10.1137/15M1032077

M3 - Article

AN - SCOPUS:84991010767

VL - 45

SP - 1171

EP - 1229

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -