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

J 2024

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

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ

Basic information

Original name

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

Authors

BALABÁN, Jakub (203 Czech Republic, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Jan JEDELSKÝ (203 Czech Republic, belonging to the institution)

Edition

DISCRETE MATHEMATICS, NETHERLANDS, ELSEVIER, 2024, 0012-365X

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Netherlands

Confidentiality degree

is not subject to a state or trade secret

References:

arXiv preprint

Impact factor

Impact factor: 0.700 in 2023

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1016/j.disc.2024.113876

UT WoS

001252097100001

Keywords in English

twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence

Abstract

V originále

The new graph parameter twin-width, introduced by Bonnet, Kim, Thomassé and Watrigant in 2020, 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, classes of efficiently bounded 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 slight subclass of k-mixed-thin graphs is transduction-equivalent to posets of width such that there is a quadratic-polynomial relation between k and . In addition to that, we also give an abstract overview of the so-called red potential method which we use to prove our twin-width bounds.

Links

GA20-04567S, research and development project

Name: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Czech Science Foundation

MUNI/A/1592/2023, interní kód MU

Name: Modelování, analýza a verifikace (2024)

Investor: Masaryk University, Modeling, analysis, and verification (2024)

MUNI/A/1608/2023, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Investor: Masaryk University

Citovat

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. DISCRETE MATHEMATICS. NETHERLANDS: ELSEVIER, 2024, vol. 347, No 8, p. 113876-113895. ISSN 0012-365X. Available from: https://dx.doi.org/10.1016/j.disc.2024.113876.

@article{2374737,
   author = {Balabán, Jakub and Hliněný, Petr and Jedelský, Jan},
   article_location = {NETHERLANDS},
   article_number = {8},
   doi = {http://dx.doi.org/10.1016/j.disc.2024.113876},
   keywords = {twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence},
   language = {eng},
   issn = {0012-365X},
   journal = {DISCRETE MATHEMATICS},
   title = {Twin-Width and Transductions of Proper k-Mixed-Thin Graphs},
   url = {https://arxiv.org/abs/2202.12536},
   volume = {347},
   year = {2024}
}

TY  - JOUR
ID  - 2374737
AU  - Balabán, Jakub - Hliněný, Petr - Jedelský, Jan
PY  - 2024
TI  - Twin-Width and Transductions of Proper k-Mixed-Thin Graphs
JF  - DISCRETE MATHEMATICS
VL  - 347
IS  - 8
SP  - 113876
EP  - 113876
PB  - ELSEVIER
SN  - 0012365X
KW  - twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
UR  - https://arxiv.org/abs/2202.12536
N2  - The new graph parameter twin-width, introduced by Bonnet, Kim, Thomassé and Watrigant in 2020, 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, classes of efficiently bounded 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 slight subclass of k-mixed-thin graphs is transduction-equivalent to posets of width such that there is a quadratic-polynomial relation between k and . In addition to that, we also give an abstract overview of the so-called red potential method which we use to prove our twin-width bounds.
ER  -

BALABÁN, Jakub, Petr HLINĚNÝ and Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. \textit{DISCRETE MATHEMATICS}. NETHERLANDS: ELSEVIER, 2024, vol.~347, No~8, p.~113876-113895. ISSN~0012-365X. Available from: https://dx.doi.org/10.1016/j.disc.2024.113876.

Přehled o publikaci