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
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.