FPT is characterized by useful obstruction sets

DOI10.1007/978-3-642-45043-3_23zbMATH Open1417.68051arXiv1305.3102OpenAlexW1767464984WikidataQ57359791 ScholiaQ57359791MaRDI QIDQ2864307FDOQ2864307

Authors: Michael R. Fellows, Bart M. P. Jansen 

Publication date: 6 December 2013

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1305.3102

Recommendations

• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• On problems without polynomial kernels
• Kernelization Lower Bounds by Cross-Composition
• On Problems without Polynomial Kernels (Extended Abstract)
• Cross-composition: a new technique for kernelization lower bounds

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (2)

• Sparse obstructions for minor-covering parameters
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders

This page was built for publication: FPT is characterized by useful obstruction sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864307)