FPT is Characterized by Useful Obstruction Sets

Michael Fellows, Bart Jansen

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    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. � 2013 Springer-Verlag.
    Original languageEnglish
    Title of host publicationInternational Workshop on Graph-Theoretic Concepts in Computer Science WG 2013
    Subtitle of host publication Graph-Theoretic Concepts in Computer Science
    EditorsAndreas Brandstädt, Klaus Jansen, Rüdiger Reischuk
    Place of PublicationGermany
    PublisherSpringer
    Pages261-273
    Number of pages13
    ISBN (Electronic)978-3-642-45043-3
    ISBN (Print)978-3-642-45042-6
    DOIs
    Publication statusPublished - 2013
    EventInternational Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013 39th) - Lubeck, Germany, Lubeck, Germany
    Duration: 19 Jun 201321 Jun 2013
    Conference number: 2013 (39th)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume8165
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013 39th)
    Abbreviated titleWG
    CountryGermany
    CityLubeck
    Period19/06/1321/06/13

    Fingerprint Dive into the research topics of 'FPT is Characterized by Useful Obstruction Sets'. Together they form a unique fingerprint.

    Cite this