Designing FPT Algorithms for Cut Problems Using Randomized Contractions
Authors:
- Rajesh ChitnisRCRajesh Chitnis
- Marek CyganMCMarek Cygan
- MohammadTaghi HajiaghayiMHMohammadTaghi Hajiaghayi
- Marcin PilipczukMPMarcin Pilipczuk
- Michał PilipczukMPMichał Pilipczuk
- 1 January 2016
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 45 (4) , 1171-1229
Abstract
We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT al...Keywords
All Related Versions
Funding Information
- Narodowe Centrum Nauki (N206567140)
- Fundacja na rzecz Nauki Polskiej (START)
- Defense Advanced Research Projects Agency (FA8650-11-1-7162)
- Office of Naval Research (YIP N000141110662)
- European Research Council
- National Science Foundation (CAREER 1053605)
This publication has 46 references indexed in Scilit:
- Subexponential Algorithms for Unique Games and Related ProblemsJournal of the ACM, 2015
- Directed Subset Feedback Vertex Set Is Fixed-Parameter TractableACM Transactions on Algorithms, 2015
- On multiway cut parameterized above lower boundsACM Transactions on Computation Theory, 2013
- Subset Feedback Vertex Set Is Fixed-Parameter TractableSIAM Journal on Discrete Mathematics, 2013
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the CutsetSIAM Journal on Computing, 2013
- Near-optimal algorithms for maximum constraint satisfaction problemsACM Transactions on Algorithms, 2009
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut ProblemAlgorithmica, 2007
- The Steiner k-Cut ProblemSIAM Journal on Discrete Mathematics, 2006
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set ProblemSIAM Journal on Discrete Mathematics, 1999
- Color-codingJournal of the ACM, 1995