Finite Integer Index of Pathwidth and Treewidth

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ORDYNIAK Sebastian GAJARSKÝ Jakub REIDL Felix ROSSMANITH Peter OBDRŽÁLEK Jan SÁNCHEZ VILAAMIL Fernando

Year of publication 2014
Type Article in Proceedings
Conference IPEC 2014, LNCS 8246
MU Faculty or unit

Faculty of Informatics

Citation ORDYNIAK, Sebastian, Jakub GAJARSKÝ, Felix REIDL, Peter ROSSMANITH, Jan OBDRŽÁLEK and Fernando SÁNCHEZ VILAAMIL. Finite Integer Index of Pathwidth and Treewidth. In Marek Cygan and Pinar Heggernes. IPEC 2014, LNCS 8246. Wroclaw: Springer, 2014, p. 258-269. ISBN 978-3-319-13523-6. Available from: https://dx.doi.org/10.1007/978-3-319-13524-3_22.
Doi http://dx.doi.org/10.1007/978-3-319-13524-3_22
Field Informatics
Keywords meta-kernalization; finite integer index; treewidth; pathwidth
Description We show that the optimization versions of the Pathwidth and Treewidth problems have a property called finite integer index when the inputs are restricted to graphs of bounded pathwidth and bounded treewidth, respectively. They do not have this property in general graph classes. This has interesting consequences for kernelization of both these (optimization) problems on certain sparse graph classes. In the process we uncover an interesting property of path and tree decompositions, which might be of independent interest.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

By clicking “Accept Cookies”, you agree to the storing of cookies on your device to enhance site navigation, analyze site usage, and assist in our marketing efforts. Cookie Settings

Necessary Only Accept Cookies