Designing FPT algorithms for cut problems using randomized contractions
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 84878050
- Type
- D - Journal article
- DOI
-
10.1137/15M1032077
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 1171
- Volume
- 45
- Issue
- 4
- ISSN
- 0097-5397
- Open access status
- Deposit exception
- Month of publication
- July
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
-
- Citation count
- 21
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper developed a new technique called "randomized contractions" for designing fixed-parameter tractable (FPT) algorithms for graph problems. An extended abstract of the paper appeared at the 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), which is the leading theoretical computer science conference. The principal outcome of the paper is the first FPT algorithm for the parameterized version of the Unique Label Cover problem, which forms the basis of the Unique Games Conjecture. Several follow-up papers have since used this technique to resolve the FPT status of important problems such as Minimum Bisection, Mixed-Cut and List Digraph Homomorphism.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -