Search Results

Documents authored by Rocton, Mathis

Document
DOI: 10.4230/LIPIcs.STACS.2026.42
Computing Twin-Width via Treedepth and Vertex Integrity

Authors: Robert Ganian and Mathis Rocton

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.
Cite as

Robert Ganian and Mathis Rocton. Computing Twin-Width via Treedepth and Vertex Integrity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2026.42,
  author =	{Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width via Treedepth and Vertex Integrity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.42},
  URN =		{urn:nbn:de:0030-drops-255318},
  doi =		{10.4230/LIPIcs.STACS.2026.42},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, treedepth, vertex integrity}
}
Artifact
Software
DOI: 10.4230/artifacts.25245
The (not-so) Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton

Abstract
Cite as

Alexander Dobler, Simon Dominik Fink, Mathis Rocton. The (not-so) Bad Dominating Set Maker (Software, source code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25245,
   title = {{The (not-so) Bad Dominating Set Maker}}, 
   author = {Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
   note = {Software, Vienna Science and Technology Fund (WWTF) grant [10.47379/ICT19035], Vienna Science and Technology Fund (WWTF) grant [10.47379/ICT22029], European Union’s Horizon 2020 research and innovation COFUND programme (LogiCS@TUWien, grant agreement No 101034440), Austrian Science Fund (FWF) grant [10.55776/Y1329], swhId: \href{https://archive.softwareheritage.org/swh:1:dir:77b0720cd14b92e8d17e114ccf5c1ea89f79dfc9;origin=https://github.com/Doblalex/pace2025;visit=swh:1:snp:db5069228cfc618259ba32a9fe127fd1cb8ef66f;anchor=swh:1:rev:9d5280950b6d22bf75cddbc5bb9d41303b5ba4da}{\texttt{swh:1:dir:77b0720cd14b92e8d17e114ccf5c1ea89f79dfc9}} (visited on 2025-12-15)},
   url = {https://github.com/Doblalex/pace2025},
   doi = {10.4230/artifacts.25245},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.35
PACE Solver Description: Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Dominating Set and Hitting Set are two well-known NP-hard problems on graphs and hypergraphs, respectively. For Dominating Set, we seek a subset S of vertices of minimum size, such that every vertex has a neighbor in S. For Hitting Set, we require that this minimum size subset S intersects each hyperedge. We present Bad Dominating Set Maker, our solver for both problems posed in the exact tracks of the 2025 PACE Challenge. It uses reduction rules, dynamic programming on tree decompositions, and external Vertex Cover and SAT solvers.
Cite as

Alexander Dobler, Simon Dominik Fink, and Mathis Rocton. PACE Solver Description: Bad Dominating Set Maker. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.IPEC.2025.35,
  author =	{Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
  title =	{{PACE Solver Description: Bad Dominating Set Maker}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.35},
  URN =		{urn:nbn:de:0030-drops-251673},
  doi =		{10.4230/LIPIcs.IPEC.2025.35},
  annote =	{Keywords: Dominating Set, Hitting Set, Pace Challenge}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.3
Twin-Width Meets Feedback Edges and Vertex Integrity

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: - An asymptotically tight bound between twin-width and the feedback edge number; - A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency; - An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Twin-Width Meets Feedback Edges and Vertex Integrity. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.IPEC.2024.3,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Twin-Width Meets Feedback Edges and Vertex Integrity}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.3},
  URN =		{urn:nbn:de:0030-drops-222293},
  doi =		{10.4230/LIPIcs.IPEC.2024.3},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, feedback edge number, vertex integrity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.7
Computing Twin-Width Parameterized by the Feedback Edge Number

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an 𝓁-contraction sequence (for an arbitrary specified 𝓁) or determines that the twin-width of the input graph is at least 𝓁. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing Twin-Width Parameterized by the Feedback Edge Number. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.STACS.2024.7,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width Parameterized by the Feedback Edge Number}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.7},
  URN =		{urn:nbn:de:0030-drops-197170},
  doi =		{10.4230/LIPIcs.STACS.2024.7},
  annote =	{Keywords: twin-width, parameterized complexity, kernelization, feedback edge number}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.38
PACE Solver Description: Touiouidth

Authors: Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.
Cite as

Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: Touiouidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.IPEC.2023.38,
  author =	{Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Dobler, Alexander and Morelle, Laure and Reinald, Amadeus and Rocton, Mathis},
  title =	{{PACE Solver Description: Touiouidth}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{38:1--38:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.38},
  URN =		{urn:nbn:de:0030-drops-194576},
  doi =		{10.4230/LIPIcs.IPEC.2023.38},
  annote =	{Keywords: Twinwidth, Pace Challenge}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2022.31
PACE Solver Description: DreyFVS

Authors: Gabriel Bathie, Gaétan Berthe, Yoann Coudert-Osmont, David Desobry, Amadeus Reinald, and Mathis Rocton

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We describe DreyFVS, a heuristic for Directed Feedback Vertex Set submitted to the 2022 edition of Parameterized Algorithms and Computational Experiments Challenge. The Directed Feedback Vertex Set problem asks to remove a minimal number of vertices from a digraph such that the resulting digraph is acyclic. Our algorithm first performs a guess on a reduced instance by leveraging the Sinkhorn-Knopp algorithm, to then improve this solution by pipelining two local search methods.
Cite as

Gabriel Bathie, Gaétan Berthe, Yoann Coudert-Osmont, David Desobry, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: DreyFVS. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bathie_et_al:LIPIcs.IPEC.2022.31,
  author =	{Bathie, Gabriel and Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Desobry, David and Reinald, Amadeus and Rocton, Mathis},
  title =	{{PACE Solver Description: DreyFVS}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{31:1--31:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.31},
  URN =		{urn:nbn:de:0030-drops-173870},
  doi =		{10.4230/LIPIcs.IPEC.2022.31},
  annote =	{Keywords: Directed Feedback Vertex Set, Heuristic, Sinkhorn algorithm, Local search}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact