FPT is characterized by useful obstruction sets

Connecting algorithms, kernels, and quasi-orders

Michael Fellows, Bart Jansen

    Research output: Contribution to journalArticleResearchpeer-review

    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. � 2014 ACM.
    Original languageEnglish
    Pages (from-to)1-26
    Number of pages26
    JournalACM Transactions on Computation Theory
    Volume6
    Issue number4
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Quasi-order
    Obstruction
    Polynomials
    kernel
    Chemical analysis
    Polynomial
    Graph Minors
    Kernelization
    Pathwidth
    Minor
    Trivial
    Graph in graph theory

    Cite this

    @article{993582b613c74f919ac7334bf9eefca0,
    title = "FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders",
    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. � 2014 ACM.",
    keywords = "Algorithms, FPT algorithms, Kernelization, Parameterized complexity, Parameterized problems, Pathwidth, Polynomial kernels, Polynomial size, Well-quasiordering, Polynomials",
    author = "Michael Fellows and Bart Jansen",
    year = "2014",
    doi = "10.1145/2635820",
    language = "English",
    volume = "6",
    pages = "1--26",
    journal = "ACM Transactions on Computation Theory",
    issn = "1942-3454",
    publisher = "Association for Computing Machinery (ACM)",
    number = "4",

    }

    FPT is characterized by useful obstruction sets : Connecting algorithms, kernels, and quasi-orders. / Fellows, Michael; Jansen, Bart.

    In: ACM Transactions on Computation Theory, Vol. 6, No. 4, 2014, p. 1-26.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - FPT is characterized by useful obstruction sets

    T2 - Connecting algorithms, kernels, and quasi-orders

    AU - Fellows, Michael

    AU - Jansen, Bart

    PY - 2014

    Y1 - 2014

    N2 - 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. � 2014 ACM.

    AB - 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. � 2014 ACM.

    KW - Algorithms

    KW - FPT algorithms

    KW - Kernelization

    KW - Parameterized complexity

    KW - Parameterized problems

    KW - Pathwidth

    KW - Polynomial kernels

    KW - Polynomial size

    KW - Well-quasiordering

    KW - Polynomials

    U2 - 10.1145/2635820

    DO - 10.1145/2635820

    M3 - Article

    VL - 6

    SP - 1

    EP - 26

    JO - ACM Transactions on Computation Theory

    JF - ACM Transactions on Computation Theory

    SN - 1942-3454

    IS - 4

    ER -