Solving Partial Dominating Set and Related Problems Using
Twin-Width

D 2025

Solving Partial Dominating Set and Related Problems Using Twin-Width

BALABÁN, Jakub; Daniel MOCK a Peter ROSSMANITH

Základní údaje

Originální název

Solving Partial Dominating Set and Related Problems Using Twin-Width

Autoři

BALABÁN, Jakub; Daniel MOCK a Peter ROSSMANITH

Vydání

345. vyd. Dagstuhl, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), od s. "13:1"-"13:19", 19 s. 2025

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141840

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-388-1

EID Scopus

2-s2.0-105014728348

Klíčová slova anglicky

Partial Dominating Set; Partial Vertex Cover; meta-algorithm; counting logic; twin-width

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 4. 2026 12:04, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\rm W[1]$-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form \phi\equiv\exists x_1\cdots \exists x_k \sum_{i\in I} \#y\,\psi_i(x_1,\ldots,x_k,y)\ge t$, where $\psi_i$ is a quantifier-free formula for each $i \in I$, $t$ is an arbitrary number, and $\#y$ is a counting quantifier, can be evaluated in time $f(d,k)n$, where $n$ is the number of vertices and $d$ is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.

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

BALABÁN, Jakub; Daniel MOCK a Peter ROSSMANITH. Solving Partial Dominating Set and Related Problems Using Twin-Width. Online. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak. 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). 345. vyd. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, 2025, s. "13:1"-"13:19", 19 s. ISBN 978-3-95977-388-1.

@inproceedings{2513979,
   author = {Balabán, Jakub and Mock, Daniel and Rossmanith, Peter},
   address = {Dagstuhl},
   booktitle = {50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
   edition = {345},
   editor = {Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak},
   keywords = {Partial Dominating Set; Partial Vertex Cover; meta-algorithm; counting logic; twin-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-388-1},
   pages = {"13:1"-"13:19"},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
   title = {Solving Partial Dominating Set and Related Problems Using Twin-Width},
   year = {2025}
}

TY  - CONF
ID  - 2513979
AU  - Balabán, Jakub - Mock, Daniel - Rossmanith, Peter
PY  - 2025
TI  - Solving Partial Dominating Set and Related Problems Using Twin-Width
PB  - Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
CY  - Dagstuhl
SN  - 9783959773881
KW  - Partial Dominating Set
KW  - Partial Vertex Cover
KW  - meta-algorithm
KW  - counting logic
KW  - twin-width
N2  - Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\rm W[1]$-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form \phi\equiv\exists x_1\cdots \exists x_k \sum_{i\in I} \#y\,\psi_i(x_1,\ldots,x_k,y)\ge t$, where $\psi_i$ is a quantifier-free formula for each $i \in I$, $t$ is an arbitrary number, and $\#y$ is a counting quantifier, can be evaluated in time $f(d,k)n$, where $n$ is the number of vertices and $d$ is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
ER  -

BALABÁN, Jakub; Daniel MOCK a Peter ROSSMANITH. Solving Partial Dominating Set and Related Problems Using Twin-Width. Online. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak. \textit{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)}. 345. vyd. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f$\{\backslash$''$\{$u$\}\}$r Informatik, 2025, s.~''13:1''-''13:19'', 19 s. ISBN~978-3-95977-388-1.

Přehled o publikaci