Transductions of Graph Classes Admitting Product Structure

D 2025

Transductions of Graph Classes Admitting Product Structure

HLINĚNÝ, Petr a Jan JEDELSKÝ

Základní údaje

Originální název

Transductions of Graph Classes Admitting Product Structure

Autoři

HLINĚNÝ, Petr a Jan JEDELSKÝ

Vydání

USA, 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), od s. 843-855, 13 s. 2025

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

arXiv

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

ISBN

979-8-3315-7900-5

DOI

https://doi.org/10.1109/LICS65433.2025.00069

Klíčová slova anglicky

product structure; hereditary class; clique-width; transduction

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 11. 11. 2025 15:51, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure – being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmović et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way—the latter concept being introduced just recently by authors under the name of H-clique-width [MFCS 2024].Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs.

Návaznosti

MUNI/A/1600/2024, interní kód MU

Název: Modelování, analýza a verifikace (2025)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2025)

MUNI/A/1666/2024, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Citovat

HLINĚNÝ, Petr a Jan JEDELSKÝ. Transductions of Graph Classes Admitting Product Structure. Online. In 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). USA: IEEE, 2025, s. 843-855. ISBN 979-8-3315-7900-5. Dostupné z: https://doi.org/10.1109/LICS65433.2025.00069.

@inproceedings{2532382,
   author = {Hliněný, Petr and Jedelský, Jan},
   address = {USA},
   booktitle = {40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
   doi = {https://doi.org/10.1109/LICS65433.2025.00069},
   keywords = {product structure; hereditary class; clique-width; transduction},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {979-8-3315-7900-5},
   pages = {843-855},
   publisher = {IEEE},
   title = {Transductions of Graph Classes Admitting Product Structure},
   url = {https://arxiv.org/abs/2501.18326},
   year = {2025}
}

TY  - CONF
ID  - 2532382
AU  - Hliněný, Petr - Jedelský, Jan
PY  - 2025
TI  - Transductions of Graph Classes Admitting Product Structure
PB  - IEEE
CY  - USA
SN  - 9798331579005
KW  - product structure
KW  - hereditary class
KW  - clique-width
KW  - transduction
UR  - https://arxiv.org/abs/2501.18326
N2  - In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure – being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmović et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way—the latter concept being introduced just recently by authors under the name of H-clique-width [MFCS 2024].Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs.
ER  -

HLINĚNÝ, Petr a Jan JEDELSKÝ. Transductions of Graph Classes Admitting Product Structure. Online. In \textit{40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}. USA: IEEE, 2025, s.~843-855. ISBN~979-8-3315-7900-5. Dostupné z: https://doi.org/10.1109/LICS65433.2025.00069.

Přehled o publikaci