Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

FPT is characterized by useful obstruction sets

Fellows, Michael R. and Jansen, Bart (2013). FPT is characterized by useful obstruction sets. In: Graph-Theoretic Concepts in Computer Science 39th International Workshop WG 2013, Lübeck, Germany, 19-21 June 2013.

Document type: Conference Paper

IRMA ID 82794376xPUB260
Author Fellows, Michael R.
Jansen, Bart
Title FPT is characterized by useful obstruction sets
Conference Name Graph-Theoretic Concepts in Computer Science 39th International Workshop WG 2013
Conference Location Lübeck, Germany
Conference Dates 19-21 June 2013
Conference Publication Title Theoretical Computer Science and General Issues, Advanced Research in Computing and Software Science
Place of Publication Germany
Publisher Springer
Publication Year 2013
ISBN 978-3-642-45042-6   (check CDU catalogue open catalogue search in new window)
Start Page 261
End Page 273
Total Pages 13
HERDC Category E1 - Conference Publication (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 -̨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.
Additional Notes Series: Lecture Notes in Computer Science, Vol. 8165
Description for Link Link to conference homepage
Version Filter Type
Access Statistics: 221 Abstract Views, 7 File Downloads  -  Detailed Statistics
Created: Thu, 07 Aug 2014, 16:39:54 CST