### Abstract

Original language | English |
---|---|

Pages (from-to) | 1-26 |

Number of pages | 26 |

Journal | ACM Transactions on Computation Theory |

Volume | 6 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2014 |

### Fingerprint

### Cite this

*ACM Transactions on Computation Theory*,

*6*(4), 1-26. https://doi.org/10.1145/2635820

}

*ACM Transactions on Computation Theory*, vol. 6, no. 4, pp. 1-26. https://doi.org/10.1145/2635820

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

Research output: Contribution to journal › Article › Research › peer-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 -