Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

Varování

Publikace nespadá pod Lékařskou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	BALABÁN Jakub HLINĚNÝ Petr JEDELSKÝ Jan
Rok publikování	2022
Druh	Článek ve sborníku
Konference	WG 2022: Graph-Theoretic Concepts in Computer Science
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	https://arxiv.org/abs/2202.12536 https://link.springer.com/chapter/10.1007/978-3-031-15914-5_4
Doi	http://dx.doi.org/10.1007/978-3-031-15914-5_4
Klíčová slova	twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
Popis	The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width ??' such that there is a quadratic relation between k and ??'.
Související projekty:	Structure of tractable instances of hard algorithmic problems on graphs Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 22 Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.