Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders

Fellows, Michael and Jansen, Bart M. P. (2014). FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders. ACM Transactions on Computation Theory,6(4 - Article No. 16):1-26.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 75039815xPUB526
Title FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders
Author Fellows, Michael
Jansen, Bart M. P.
Journal Name ACM Transactions on Computation Theory
Publication Date 2014
Volume Number 6
Issue Number 4 - Article No. 16
ISSN 1942-3454   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84906513775
Start Page 1
End Page 26
Total Pages 26
Place of Publication United States
Publisher A C M Special Interest Group
HERDC Category C1 - Journal Article (DIISR)
Abstract Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable obstruction sets and efficient order tests is not just one way of obtaining strongly uniform FPT algorithms, but that all of FPT may be captured in this way. Our new characterization of FPT has a strong connection to the theory of kernelization, as we prove that problems with polynomial kernels can be characterized by obstruction sets whose elements have polynomial size. Consequently we investigate the interplay between the sizes of problem kernels and the sizes of the elements of such obstruction sets, obtaining several examples of how results in one area yield new insights in the other. We show how exponential-size minor-minimal obstructions for pathwidth k form the crucial ingredient in a novel or-cross-composition for k-Pathwidth, complementing the trivial and-composition that is known for this problem. In the other direction, we show that or-cross-compositions into a parameterized problem can be used to rule out the existence of efficiently generated quasi-orders on its instances that characterize the no-instances by polynomial-size obstructions.
DOI http://dx.doi.org/10.1145/2635820   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 14 Abstract Views  -  Detailed Statistics
Created: Wed, 19 Aug 2015, 12:16:45 CST