research-article

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

Authors:

Michael R. Fellows,

Bart M. P. JansenAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 6, Issue 4

Article No.: 16, Pages 1 - 26

https://doi.org/10.1145/2635820

Published: 01 August 2014 Publication History

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.

References

[1]

Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters. 2007. Crown structures for vertex cover kernelization. Theory Comput. Syst. 41, 3, 411--430.

Digital Library

[2]

Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. 1987. Complexity of finding embeddings in a k-tree. SIAM J. Algebra. Discr. 8, 277--284.

Digital Library

[3]

Hans L. Bodlaender. 1998. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1--2, 1--45.

Digital Library

[4]

Hans L. Bodlaender. 2009. Kernelization: New upper and lower bound techniques. In Proceedings of 4th IWPEC. 17--37.

Digital Library

[5]

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. 2009a. On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 8, 423--434.

Digital Library

[6]

Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. 2009b. (Meta) Kernelization. In Proceedings of 50th FOCS. 629--638.

Digital Library

[7]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2011. Cross-composition: a new technique for kernelization lower bounds. In Proceedings of 28th STACS. 165--176.

[8]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2012. Kernel bounds for structural parameterizations of pathwidth. In Proceedings of 13th SWAT. 352--363.

Digital Library

[9]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2013. Preprocessing for treewidth: A combinatorial analysis through kernelization. SIAM J. Discrete Math. 27, 4, 2108--2142.

[10]

Hans L. Bodlaender and Ton Kloks. 1996. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algor. 21, 2, 358--402.

Digital Library

[11]

Hans L. Bodlaender and Rolf H. Möhring. 1993. The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 6, 181--188.

Digital Library

[12]

Kevin Cattell, Michael J. Dinneen, Rodney G. Downey, Michael R. Fellows, and Michael A. Langston. 2000. On computing graph minor obstruction sets. Theor. Comput. Sci. 233, 107--127.

Digital Library

[13]

Jianer Chen, Iyad A. Kanj, and Weijia Jia. 2001. Vertex cover: Further observations and further improvements. J. Algor. 41, 2, 280--301.

Digital Library

[14]

Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55, 5.

Digital Library

[15]

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. 2012. Clique cover and graph separation: New incompressibility results. In Proceedings of 39th ICALP. 254--265.

Digital Library

[16]

Holger Dell and Dániel Marx. 2012. Kernelization of packing problems. In Proceedings of 23rd SIAM SODA. 68--81.

Digital Library

[17]

Holger Dell and Dieter van Melkebeek. 2010. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In Proceedings of 42nd STOC. 251--260.

Digital Library

[18]

Reinhard Diestel. 2010. Graph Theory 4th Ed. Springer-Verlag, Heidelberg.

[19]

Michael J. Dinneen. 1997. Too many minor order obstructions. J. Univers. Comput. Sci. 3, 1199--1206.

[20]

Michael J. Dinneen, Kevin Cattell, and Michael R. Fellows. 2001. Forbidden minors to graphs with small feedback sets. Discrete Math. 230, 1--3, 215--252.

[21]

Michael J. Dinneen and Rongwei Lai. 2007. Properties of vertex cover obstructions. Discrete Math. 307, 21, 2484--2500

Digital Library

[22]

Michael J. Dinneen and Liu Xiong. 2002. Minor-order obstructions for the graphs of vertex cover 6. J. Graph Theory 41, 3, 163--178.

Digital Library

[23]

Rod Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, New York.

Digital Library

[24]

Andrew Drucker. 2012. New limits to classical and quantum instance compression. In Proceedings of 53rd FOCS. 609--618

Digital Library

[25]

Zdenek Dvorak, Archontia C. Giannopoulou, and Dimitrios M. Thilikos. 2012. Forbidden graphs for tree-depth. Euro. J. Comb. 33, 5, 969--979.

Digital Library

[26]

Paul Erdős and Tibor Gallai. 1961. On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hung. Acad. Sci., Ser. A 6, 181--203.

[27]

Michael R. Fellows, Bart M. P. Jansen, and Frances Rosamond. 2013. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Euro. J. Combin. 34, 3, 541--566.

Digital Library

[28]

Michael R. Fellows and Michael A. Langston. 1988. Nonconstructive tools for proving polynomial-time decidability. J. ACM 35, 3, 727--739.

Digital Library

[29]

Michael R. Fellows and Michael A. Langston. 1989. An analogue of the Myhill-Nerode Theorem and its use in computing finite-basis characterizations (extended abstract). In Proceedings of 30th FOCS. 520--525.

Digital Library

[30]

Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, New York.

Digital Library

[31]

Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. 2014. Preprocessing subgraph and minor problems: When does a small vertex cover help? J. Comput. Syst. Sci. 80, 2, 468--495.

Digital Library

[32]

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of 53rd FOCS. 470--479.

Digital Library

[33]

Lance Fortnow and Rahul Santhanam. 2011. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77, 1, 91--106.

Digital Library

[34]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.

Digital Library

[35]

Jiong Guo and Rolf Niedermeier. 2007. Invitation to data reduction and problem kernelization. SIGACT News 38, 1, 31--45.

Digital Library

[36]

Danny Harnik and Moni Naor. 2010. On the compressibility of NP instances and cryptographic applications. SIAM J. Comput. 39, 5, 1667--1713.

Digital Library

[37]

Danny Hermelin and Xi Wu. 2012. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of 23rd SODA. 104--113.

Digital Library

[38]

Bart M. P. Jansen. 2013. On sparsification for computing treewidth. In Proceedings of 8th IPEC. 216--229.

[39]

Bart M. P. Jansen and Stefan Kratsch. 2013. Data reduction for graph coloring problems. Inform. Comput. 231, 0, 70--88.

Digital Library

[40]

Nancy G. Kinnersley. 1992. The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42, 6, 345--350.

Digital Library

[41]

Stefan Kratsch. 2012. Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. In Proceedings of 23rd SODA. 114--122.

Digital Library

[42]

Stefan Kratsch. 2014. Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. ACM Trans. Algor. 1--13. To appear.

Digital Library

[43]

Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, and Venkatesh Raman. 2012. Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. In Proceedings of 13th SWAT. 364--375.

Digital Library

[44]

Stefan Kratsch and Magnus Wahlström. 2011. The AND-conjecture may be necessary. In Parameterized Complexity Newsletter. FPT Wiki, Darwin.

[45]

Stefan Kratsch and Magnus Wahlström. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of 53rd FOCS. 450--459.

Digital Library

[46]

Jens Lagergren. 1998. Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B 73, 1, 7--40.

Digital Library

[47]

Choongbum Lee. 2009. On the size of minimal unsatisfiable formulas. Electr. J. Comb. 16, 1.

[48]

Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, 129--161.

[49]

László Lovász and Michael D. Plummer. 1986. Matching Theory. Annals of Discrete Mathematics, Vol. 29. North-Holland Publishing Co., Amsterdam, The Netherlands.

[50]

Neil Robertson and Paul D. Seymour. 1983. Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B 35, 1, 39--61.

[51]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B 41, 1, 92--114.

Digital Library

[52]

Neil Robertson and Paul D. Seymour. 1995. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B 63, 1, 65--110.

Digital Library

[53]

Neil Robertson and Paul D. Seymour. 2004. Graph Minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B 92, 2, 325--357.

Digital Library

[54]

Juanjo Rué, Konstantinos S. Stavropoulos, and Dimitrios M. Thilikos. 2012. Outerplanar obstructions for a feedback vertex set. Eur. J. Comb. 33, 5, 948--968.

Digital Library

[55]

Atsushi Takahashi, Shuichi Ueno, and Yoji Kajitani. 1994. Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Math. 127, 293--304.

Digital Library

[56]

Chee-Keng Yap. 1983. Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287--300.

Cited By

Sau IStamoulis GThilikos D(2023) k-apices of minor-closed graph classes. I. Bounding the obstructionsJournal of Combinatorial Theory Series B10.1016/j.jctb.2023.02.012161:C(180-227)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jctb.2023.02.012
Leivaditis ASingh AStamoulis GThilikos DTsatsanis K(2021)Minor obstructions for apex-pseudoforestsDiscrete Mathematics10.1016/j.disc.2021.112529344:10Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1016/j.disc.2021.112529
Giannopoulou AJansen BLokshtanov DSaurabh S(2017)Uniform Kernelization Complexity of Hitting Forbidden MinorsACM Transactions on Algorithms10.1145/302905113:3(1-35)Online publication date: 20-Mar-2017
https://dl.acm.org/doi/10.1145/3029051
Show More Cited By

Index Terms

FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Randomness, geometry and discrete structures

Recommendations

On some FPT problems without polynomial Turing compressions
Abstract
An impressive hardness theory which can prove compression lower bounds for a large number of FPT problems has been established under the assumption that NP ⊈ coNP/poly. However, there are no problems in FPT for which the existence of ...
Kernelization Lower Bounds Through Colors and IDs

In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem

The field of kernelization offers a rigorous way of studying the ubiquitous technique of data reduction and preprocessing for combinatorially hard problems. A widely accepted definition of useful data reduction is that of a polynomial kernelization ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 6, Issue 4

August 2014

99 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2661796

Editor:
Eric Allender
Rutgers University, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2014

Accepted: 01 March 2014

Received: 01 October 2013

Published in TOCT Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sau IStamoulis GThilikos D(2023) k-apices of minor-closed graph classes. I. Bounding the obstructionsJournal of Combinatorial Theory Series B10.1016/j.jctb.2023.02.012161:C(180-227)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jctb.2023.02.012
Leivaditis ASingh AStamoulis GThilikos DTsatsanis K(2021)Minor obstructions for apex-pseudoforestsDiscrete Mathematics10.1016/j.disc.2021.112529344:10Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1016/j.disc.2021.112529
Giannopoulou AJansen BLokshtanov DSaurabh S(2017)Uniform Kernelization Complexity of Hitting Forbidden MinorsACM Transactions on Algorithms10.1145/302905113:3(1-35)Online publication date: 20-Mar-2017
https://dl.acm.org/doi/10.1145/3029051
Jansen BPieterse A(2017)Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SATAlgorithmica10.1007/s00453-016-0189-979:1(3-28)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00453-016-0189-9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents