Irrelevant vertices for the planar Disjoint Paths Problem
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-3343
- Type
- D - Journal article
- DOI
-
10.1016/j.jctb.2016.10.001
- Title of journal
- Journal of Combinatorial Theory, Series B
- Article number
- -
- First page
- 815
- Volume
- 122
- Issue
- -
- ISSN
- 0095-8956
- Open access status
- Compliant
- Month of publication
- October
- 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
-
5
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 9
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The disjoint paths problem is a classical algorithmic problem, proven to be NP-complete by Karp in the early 1970s. It asks for disjoint paths connecting predescribed graph vertices. In their famous graph minor project, Robertson and Seymour proved that this problem is fixed-parameter tractable. However, their parameter-dependence is a huge function.
The significance of this paper is that we give the fastest fixed-parameter algorithm for the problem on *planar* graphs, with moderate parameter dependence. Our correctness proof achieves a significant simplification. In particular, the conference version of this paper inspired a result for planar *directed* graphs, 10.1109/FOCS.2013.29, FOCS 2013.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
