72 Search Results for "Rzążewski, Paweł"

Volume

LIPIcs, Volume 376

52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

WG 2026, Kortrijk, Belgium, June 2-4, 2026

Editors: Jan Goedgebeur and Paweł Rzążewski

Volume

LIPIcs, Volume 321

19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

IPEC 2024, September 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom

Editors: Édouard Bonnet and Paweł Rzążewski

Document
Complete Volume
DOI: 10.4230/LIPIcs.WG.2026
LIPIcs, Volume 376, WG 2026, Complete Volume

Authors: Jan Goedgebeur and Paweł Rzążewski

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
LIPIcs, Volume 376, WG 2026, Complete Volume
Cite as

52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 1-552, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Proceedings{goedgebeur_et_al:LIPIcs.WG.2026,
  title =	{{LIPIcs, Volume 376, WG 2026, Complete Volume}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{1--552},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan 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.WG.2026},
  URN =		{urn:nbn:de:0030-drops-269591},
  doi =		{10.4230/LIPIcs.WG.2026},
  annote =	{Keywords: LIPIcs, Volume 376, WG 2026, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.WG.2026.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Jan Goedgebeur and Paweł Rzążewski

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{goedgebeur_et_al:LIPIcs.WG.2026.0,
  author =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan 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.WG.2026.0},
  URN =		{urn:nbn:de:0030-drops-269587},
  doi =		{10.4230/LIPIcs.WG.2026.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.14
K-Hole Separation in PEO‑Based ILP Treewidth Formulation

Authors: Andrea D'Ascenzo

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
In this paper, we introduce a family of valid inequalities for the strongest currently known integer programming formulation of treewidth based on perfect elimination orderings. These inequalities arise from the structure of induced chordless cycles (holes) and strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. To handle the exponentially many such inequalities, we develop a dedicated separation routine capable of detecting violated k-hole constraints within a cutting-plane framework. Our computational results show that incorporating these inequalities substantially improves the quality of the lower bounds across a broad range of graph classes, in some cases nearly closing the integrality gap.
Cite as

Andrea D'Ascenzo. K-Hole Separation in PEO‑Based ILP Treewidth Formulation. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dascenzo:LIPIcs.SEA.2026.14,
  author =	{D'Ascenzo, Andrea},
  title =	{{K-Hole Separation in PEO‑Based ILP Treewidth Formulation}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.14},
  URN =		{urn:nbn:de:0030-drops-260186},
  doi =		{10.4230/LIPIcs.SEA.2026.14},
  annote =	{Keywords: Treewidth, Integer Linear Programming, Polyhedral Combinatorics, Chordal Completion, Induced Cycles}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.28
The Parameterized Complexity of Coloring Mixed Graphs

Authors: Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, and Alexander Wolff

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring c of a mixed graph G assigns a positive integer to each vertex such that c(u)≠c(v) for every edge {u,v} and c(u)<c(v) for every arc (u,v) of G. As in classical coloring, the objective is to minimize the number of colors. Thus, mixed (graph) coloring generalizes classical coloring of undirected graphs and allows for more general applications, such as scheduling with precedence constraints, modeling metabolic pathways, and process management in operating systems; see a survey by Sotskov [Mathematics, 2020]. We initiate the systematic study of the parameterized complexity of mixed coloring. We focus on structural graph parameters that lie between cliquewidth and vertex cover, primarily with respect to the underlying undirected graph. Unlike classical coloring, which is fixed-parameter tractable (FPT) parameterized by treewidth or neighborhood diversity, we show that mixed coloring is W[1]-hard for treewidth and even paraNP-hard for neighborhood diversity. To utilize the directedness of arcs, we introduce and analyze natural generalizations of neighborhood diversity and cliquewidth to mixed graphs, and show that mixed coloring becomes FPT when parameterized by (the generalized) mixed neighborhood diversity. Further, we investigate how these parameters are affected if we add transitive arcs, which do not affect colorings. Finally, we provide tight bounds on the chromatic number of mixed graphs, generalizing known bounds on mixed interval graphs.
Cite as

Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper, and Alexander Wolff. The Parameterized Complexity of Coloring Mixed Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lauerbach_et_al:LIPIcs.SWAT.2026.28,
  author =	{Lauerbach, Antonio and Junosza-Szaniawski, Konstanty and Sieper, Marie Diana and Wolff, Alexander},
  title =	{{The Parameterized Complexity of Coloring Mixed Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.28},
  URN =		{urn:nbn:de:0030-drops-260644},
  doi =		{10.4230/LIPIcs.SWAT.2026.28},
  annote =	{Keywords: Mixed Graphs, Coloring, Parameterized Complexity, Structural Graph Parameters}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.40
Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
For a set 𝒟 of disks in the plane, its disk graph G(𝒟) is the graph with vertex set 𝒟, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set 𝒟 of n weighted disks, computing a maximum independent set of G(𝒟) is NP-hard. In this paper, we present an O(n³log n)-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of 𝒟. This setting has been studied previously for disks of equal radius, for which an O(n^{37/11})-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an O(n³log² n)-time algorithm for the dispersion problem on a set of n disks in convex position: given an integer k, compute a subset of k disks that maximizes the minimum pairwise distance among all disks in the subset.
Cite as

Anastasiia Tkachenko and Haitao Wang. Maximum Independent Sets in Disk Graphs with Disks in Convex Position. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.SWAT.2026.40,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Maximum Independent Sets in Disk Graphs with Disks in Convex Position}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.40},
  URN =		{urn:nbn:de:0030-drops-260766},
  doi =		{10.4230/LIPIcs.SWAT.2026.40},
  annote =	{Keywords: disk graphs, independent sets, convex position, dispersion}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.9
QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes

Authors: Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (MWIS) in graphs with a bounded number of pairwise vertex-disjoint and non-adjacent long induced cycles. More formally, for every fixed s and t, we show a QPTAS for MWIS in graphs that exclude sC_t as an induced minor. Combining this with known results, we obtain a QPTAS for the problem of finding a largest induced subgraph of bounded treewidth with given hereditary property definable in Counting Monadic Second Order Logic, in the same classes of graphs. This is a step towards a conjecture of Gartland and Lokshtanov which asserts that for any planar graph H, graphs that exclude H as an induced minor admit a polynomial-time algorithm for the latter problem. This conjecture is notoriously open and even its weaker variants are confirmed only for very restricted graphs H.
Cite as

Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski. QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.SWAT.2026.9,
  author =	{Bonnet, \'{E}douard and Czy\.{z}ewska, Jadwiga and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.9},
  URN =		{urn:nbn:de:0030-drops-260454},
  doi =		{10.4230/LIPIcs.SWAT.2026.9},
  annote =	{Keywords: independent set, long holes, QPTAS, induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.20
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Authors: Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t).
Cite as

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SWAT.2026.20,
  author =	{Gao, Jie and Gawrychowski, Pawe{\l} and Giannopoulos, Panos and Mulzer, Wolfgang and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title =	{{Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.20},
  URN =		{urn:nbn:de:0030-drops-260563},
  doi =		{10.4230/LIPIcs.SWAT.2026.20},
  annote =	{Keywords: Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.24
Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries

Authors: Chirag Kaudan and Amir Nayyeri

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Eppstein, Goodrich, and Liu [ESA 2025] introduced a new graph parameter, called BFS-width, and gave polylogarithmic bounds on it for bounded bandwidth graphs. Their bounds naturally imply several applications, e.g. in graph reconstruction via shortest path distance queries, graph drawing, and matrix reordering. We study this parameter for a broader class of graphs, namely bounded cutwidth graphs. We prove a sublinear upper bound on the BFS-width of bounded cutwidth graphs and show that our bounds are asymptotically tight. Our upper bound implies the first deterministic algorithm for reconstructing a bounded cutwidth graph with a subquadratic number of shortest path distance queries.
Cite as

Chirag Kaudan and Amir Nayyeri. Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaudan_et_al:LIPIcs.SWAT.2026.24,
  author =	{Kaudan, Chirag and Nayyeri, Amir},
  title =	{{Cutwidth Versus BFS-Width with Applications to Graph Reconstruction from Distance Queries}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.24},
  URN =		{urn:nbn:de:0030-drops-260600},
  doi =		{10.4230/LIPIcs.SWAT.2026.24},
  annote =	{Keywords: Graph algorithms, graph theory, cutwidth, pathwidth, BFS-width}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.77
Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs

Authors: Malory Marin, Jean-Florent Raymond, and Rémi Watrigant

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the design of robust subexponential algorithms for classical connectivity problems on intersection graphs of similarly sized fat objects in ℝ^d. In this setting, each vertex corresponds to a geometric object, and two vertices are adjacent if and only if their objects intersect. We introduce a new tool for designing such algorithms, which we call a λ-linked partition. This is a partition of the vertex set into groups of highly connected vertices. Crucially, such a partition can be computed in polynomial time and does not require access to the geometric representation of the graph. We apply this framework to problems related to paths and cycles in graphs. First, we obtain the first robust ETH-tight algorithms for Hamiltonian Path and Hamiltonian Cycle, running in time 2^O(n^{1-1/d}) on intersection graphs of similarly sized fat objects in ℝ^d. This resolves an open problem of de Berg et al. [STOC 2018] and completes the study of these problems on geometric intersection graphs from the viewpoint of ETH-tight exact algorithms. We further extend our approach to the parameterized setting and design the first robust subexponential parameterized algorithm for Long Path in any fixed dimension d. More precisely, we obtain a randomized robust algorithm running in time 2^O(k^{1-1/d} log² k) n^O(1) on intersection graphs of similarly sized fat objects in ℝ^d, where k is the natural parameter. Besides λ-linked partitions, our algorithm also relies on a low-treewidth pattern covering theorem that we establish for geometric intersection graphs, which may be viewed as a refinement of a result of Marx-Pilipczuk [ESA 2017]. This structural result may be of independent interest.
Cite as

Malory Marin, Jean-Florent Raymond, and Rémi Watrigant. Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{marin_et_al:LIPIcs.SoCG.2026.77,
  author =	{Marin, Malory and Raymond, Jean-Florent and Watrigant, R\'{e}mi},
  title =	{{Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{77:1--77:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.77},
  URN =		{urn:nbn:de:0030-drops-258842},
  doi =		{10.4230/LIPIcs.SoCG.2026.77},
  annote =	{Keywords: Robust algorithms, geometric intersection graphs, subexponential FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

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

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73: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.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.74
List Coloring Ordered Graphs with Forbidden Induced Subgraphs

Authors: Marta Piecyk and Paweł Rzążewski

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

Abstract
In the List k-Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of {1,…,k}. We need to decide if G admits a proper coloring, where every vertex receives a color from its list. The complexity of the problem in classes defined by forbidding induced subgraphs is a widely studied topic in algorithmic graph theory. Recently, Hajebi, Li, and Spirkl [SIAM J. Discr. Math. 38 (2024)] initiated the study of List 3-Coloring in ordered graphs, i.e., graphs with fixed linear ordering of vertices. Forbidding ordered induced subgraphs allows us to investigate the boundary of tractability more closely. We continue this direction of research, focusing mostly on the case of List 4-Coloring. We present several algorithmic and hardness results, which altogether provide an almost complete dichotomy for classes defined by forbidding one fixed ordered graph: our investigations leave one minimal open case.
Cite as

Marta Piecyk and Paweł Rzążewski. List Coloring Ordered Graphs with Forbidden Induced Subgraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{piecyk_et_al:LIPIcs.STACS.2026.74,
  author =	{Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{List Coloring Ordered Graphs with Forbidden Induced Subgraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{74:1--74:17},
  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.74},
  URN =		{urn:nbn:de:0030-drops-255634},
  doi =		{10.4230/LIPIcs.STACS.2026.74},
  annote =	{Keywords: coloring, ordered graphs, forbidden induced subgraphs}
}
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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.107
New Greedy Spanners and Applications

Authors: Elizaveta Popova and Elad Tzalik

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We present a simple greedy procedure to compute an (α,β)-spanner for a graph G. We then show that this procedure is useful for building fault-tolerant spanners, as well as spanners for weighted graphs. Our first main result is an algorithm that, given a multigraph G, outputs an f edge fault-tolerant (k,k-1)-spanner H of size O(fn^{1+1/k}) which is tight. To our knowledge, this is the first tight result concerning the price of fault tolerance in spanners which are not multiplicative, in any model of faults. Our second main result is a new construction of a spanner for weighted graphs. We show that any weighted graph G has a subgraph H with O(n^{1+1/k}) edges such that any path P of hop-length 𝓁 in G has a replacement path P' in H of weighted length ≤ w(P)+(2k-2)w^(1/2)(P) where w(P) is the total edge weight of P, and w^(1/2) denotes the sum of the largest ⌈𝓁/2⌉ edge weights along P. Moreover, we show such approximation is optimal for shortest paths of hop-length 2. To our knowledge, this is the first construction of a "spanner" for weighted graphs that strictly improves upon the stretch of multiplicative (2k-1)-spanners for all non-adjacent vertex pairs, while maintaining the same size bound. Our technique is based on using clustering and ball-growing, which are methods commonly used in designing spanner algorithms, to analyze simple greedy algorithms. This allows us to combine the flexibility of clustering approaches with the unique properties of the greedy algorithm to get improved bounds. In particular, our methods give a very short proof that the parallel greedy spanner adds O(kn^{1+1/k}) edges, improving upon known bounds.
Cite as

Elizaveta Popova and Elad Tzalik. New Greedy Spanners and Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 107:1-107:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{popova_et_al:LIPIcs.ITCS.2026.107,
  author =	{Popova, Elizaveta and Tzalik, Elad},
  title =	{{New Greedy Spanners and Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{107:1--107:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.107},
  URN =		{urn:nbn:de:0030-drops-253945},
  doi =		{10.4230/LIPIcs.ITCS.2026.107},
  annote =	{Keywords: Graph Spanners, Greedy Algorithms}
}
  • Refine by Type
  • 70 Document/PDF
  • 38 Document/HTML
  • 2 Volume

  • Refine by Publication Year
  • 15 2026
  • 26 2025
  • 10 2024
  • 1 2023
  • 4 2022
  • Show More...

  • Refine by Author
  • 30 Rzążewski, Paweł
  • 8 Okrasa, Karolina
  • 7 Bonnet, Édouard
  • 7 Piecyk, Marta
  • 7 Pilipczuk, Marcin
  • Show More...

  • Refine by Series/Journal
  • 70 LIPIcs

  • Refine by Classification
  • 24 Theory of computation → Graph algorithms analysis
  • 24 Theory of computation → Parameterized complexity and exact algorithms
  • 17 Mathematics of computing → Graph algorithms
  • 13 Mathematics of computing → Graph coloring
  • 10 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 6 Treewidth
  • 5 Parameterized Complexity
  • 5 fine-grained complexity
  • 5 graph homomorphism
  • 4 cutwidth
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact