Finite Integer Index of Pathwidth and Treewidth

Warning

This publication doesn't include Faculty of Sports Studies. 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:	Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci