235 Search Results for "Pilipczuk, Marcin"

Volume

LIPIcs, Volume 180

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference)

Editors: Yixin Cao and Marcin Pilipczuk

Document
DOI: 10.4230/LIPIcs.STACS.2026.12
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

Authors: Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, and André Nichterlein

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

Abstract
We study τ-Bounded-Density Edge Deletion (τ-BDED), where given an undirected graph G, the task is to remove as few edges as possible to obtain a graph G' where no subgraph of G' has density more than τ. The density of a (sub)graph is the number of edges divided by the number of vertices. This problem was recently introduced and shown to be NP-hard for τ ∈ {2/3, 3/4, 1 + 1/25}, but polynomial-time solvable for τ ∈ {0,1/2,1} [Bazgan et al., JCSS 2025]. We provide a complete dichotomy with respect to the target density τ: 1) If 2τ ∈ ℕ (half-integral target density) or τ < 2/3, then τ-BDED is polynomial-time solvable. 2) Otherwise, τ-BDED is NP-hard. We complement the NP-hardness with fixed-parameter tractability with respect to the treewidth of G. Moreover, for integral target density τ ∈ ℕ, we show τ-BDED to be solvable in randomized O(m^{1 + o(1)}) time. Our algorithmic results are based on a reduction to a new general flow problem on restricted networks that, depending on τ, can be solved via Maximum s-t-Flow or General Factors. We believe this connection between these variants of flow and matching to be of independent interest.
Cite as

Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, and André Nichterlein. Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.12,
  author =	{Bentert, Matthias and Breitkopf, Tom-Lukas and Froese, Vincent and Herrmann, Anton and Nichterlein, Andr\'{e}},
  title =	{{Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-255012},
  doi =		{10.4230/LIPIcs.STACS.2026.12},
  annote =	{Keywords: Transshipment, Maximum Flow, General Factors, Matching, Graph Modification Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

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

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  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.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.10
A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths

Authors: Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet

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

Abstract
Dumas, Foucaud, Perez and Todinca [SIAM J. Disc. Math., 2024] recently proved that every graph whose edge set can be covered by k shortest paths has pathwidth at most 3^k. In this paper, we improve this upper bound on the pathwidth to a polynomial bound; namely, we show that every graph whose edge set can be covered by k shortest paths has pathwidth O(k⁴), answering a question from the same paper. Moreover, we also prove that when k ≤ 3, every such graph has pathwidth at most k (and this bound is tight). Eventually, we show that even though there exist graphs with arbitrary large treewidth whose vertex set can be covered by 2 isometric trees, every graph whose set of edges can be covered by 2 isometric trees has treewidth at most 2.
Cite as

Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet. A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.STACS.2026.10,
  author =	{Baste, Julien and De Meyer, Lucas and Giocanti, Ugo and Objois, Etienne and Picavet, Timoth\'{e}},
  title =	{{A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-254999},
  doi =		{10.4230/LIPIcs.STACS.2026.10},
  annote =	{Keywords: Structural Graph Theory, Coverings, Metrics, Pathwidth, Treewdidth, Parameterized Algorithms, Layerings}
}
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.79
Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More

Authors: Mihail Stoian

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

Abstract
Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems have recently witnessed the sought-after speedups. Currently, the only way to repurpose the algorithm of the unweighted version for the weighted version is to employ a polynomial embedding of the input weights. This, however, introduces a pseudo-polynomial factor into the running time, which becomes impractical for arbitrarily weighted instances. In this paper, we introduce a new way to repurpose the algorithm of the unweighted problem. Specifically, we show that the time complexity of several well-known NP-hard problems operating over the (min, +) and (max, +) semirings, such as TSP, Weighted Max-Cut, and Edge-Weighted k-Clique, is proportional to that of their unweighted versions when the set of input weights has small doubling. We achieve this by a meta-algorithm that converts the input weights into polynomially bounded integers using the recent constructive Freiman’s theorem by Randolph and Węgrzycki [ESA 2024] before applying the polynomial embedding.
Cite as

Mihail Stoian. Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{stoian:LIPIcs.STACS.2026.79,
  author =	{Stoian, Mihail},
  title =	{{Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{79:1--79:19},
  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.79},
  URN =		{urn:nbn:de:0030-drops-255680},
  doi =		{10.4230/LIPIcs.STACS.2026.79},
  annote =	{Keywords: doubling constant parametrization, weighted problems, traveling salesman, weighted max-cut, edge-weighted k-clique}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.78
Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

Authors: Roohani Sharma and Michał Włodarczyk

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

Abstract
Let ℱ be a finite family of graphs. In the ℱ-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no minor from the family ℱ. This may be regarded as a far-reaching generalization of Vertex Cover and Feedback vertex Set. In their seminal work, Fomin, Lokshtanov, Misra & Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family ℱ contains a planar graph. As the size of their kernel is g(ℱ) ⋅ k^{f(ℱ)}, a natural follow-up question was whether the dependence on ℱ in the exponent of k can be avoided. The answer turned out to be negative: Giannopoulou, Jansen, Lokshtanov & Saurabh [TALG 2017] proved that this is already inevitable for the special case of the Treewidth-η-Deletion problem. In this work, we show that this non-uniformity can be avoided at the expense of a small loss. First, we present a simple 2-approximate kernelization algorithm for Treewidth-η-Deletion with a kernel size g(η) ⋅ k⁶. Next, we show that the approximation factor can be made arbitrarily close to 1, if we settle for a kernelization protocol with 𝒪(1) calls to an oracle that solves instances of size bounded by a uniform polynomial in k. We extend the above results to general ℱ-Deletion, whenever ℱ contains a planar graph, as long as an oracle for Treewidth-η-Deletion is available for small instances. Notably, all our constants are computable functions of ℱ and our techniques work also when some graphs in ℱ may be disconnected. Our results rely on two novel techniques. First, we transform so-called "near-protrusion decompositions" into true protrusion decompositions by sacrificing a small accuracy loss. Secondly, we show how to optimally compress such a decomposition with respect to general ℱ-Deletion. Using our second technique, we also obtain linear kernels on sparse graph classes when ℱ contains a planar graph, whereas the previously known theorems required all graphs in ℱ to be connected. Specifically, we generalize the kernelization algorithm by Kim, Langer, Paul, Reidl, Rossmanith, Sau & Sikdar [TALG 2015] on graph classes that exclude a topological minor.
Cite as

Roohani Sharma and Michał Włodarczyk. Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 78:1-78:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sharma_et_al:LIPIcs.STACS.2026.78,
  author =	{Sharma, Roohani and W{\l}odarczyk, Micha{\l}},
  title =	{{Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{78:1--78:21},
  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.78},
  URN =		{urn:nbn:de:0030-drops-255674},
  doi =		{10.4230/LIPIcs.STACS.2026.78},
  annote =	{Keywords: kernelization, graph minors, treewidth, uniform kernels, minor hitting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.24
Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics

Authors: Justine Cauvi, Nils Morawietz, and Laurent Viennot

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

Abstract
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.
Cite as

Justine Cauvi, Nils Morawietz, and Laurent Viennot. Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:LIPIcs.STACS.2026.24,
  author =	{Cauvi, Justine and Morawietz, Nils and Viennot, Laurent},
  title =	{{Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{24:1--24:19},
  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.24},
  URN =		{urn:nbn:de:0030-drops-255139},
  doi =		{10.4230/LIPIcs.STACS.2026.24},
  annote =	{Keywords: network design, temporal paths, foremost paths, fastest paths, shortest paths, non-strict paths, periodic temporal graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.19
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Authors: Nicolas Bousquet and Daniel W. Cranston

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

Abstract
Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.
Cite as

Nicolas Bousquet and Daniel W. Cranston. A Linear Kernel for Independent Set Reconfiguration in Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2026.19,
  author =	{Bousquet, Nicolas and Cranston, Daniel W.},
  title =	{{A Linear Kernel for Independent Set Reconfiguration in Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{19:1--19:18},
  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.19},
  URN =		{urn:nbn:de:0030-drops-255081},
  doi =		{10.4230/LIPIcs.STACS.2026.19},
  annote =	{Keywords: Reconfiguration, Independent Set, Kernel, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.67
Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata

Authors: Filip Mazowiecki, Antoni Puch, and Daniel Smertnig

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

Abstract
In this work we consider two rich subclasses of weighted automata over fields: polynomially ambiguous weighted automata and copyless cost register automata. Primarily we are interested in understanding their expressiveness power. Over the field of rationals and 1-letter alphabets, it is known that the two classes coincide; they are equivalent to linear recurrence sequences (LRS) whose exponential bases are roots of rationals. We develop a tool we call Pumping Sequence Families, which, by exploiting the simple single-letter behaviour of the models, yields two pumping-like results over arbitrary fields with unrestricted alphabets, one for each class. As a corollary of these results, we present examples proving that the two classes become incomparable over the field of rationals with unrestricted alphabets. We complement the results by analysing the zeroness and equivalence problems. For weighted automata (even unrestricted) these problems are well understood: there are polynomial time, and even NC² algorithms. For copyless cost register automata we show that the two problems are PSpace-complete, where the difficulty is to show the lower bound.
Cite as

Filip Mazowiecki, Antoni Puch, and Daniel Smertnig. Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mazowiecki_et_al:LIPIcs.STACS.2026.67,
  author =	{Mazowiecki, Filip and Puch, Antoni and Smertnig, Daniel},
  title =	{{Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{67:1--67:21},
  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.67},
  URN =		{urn:nbn:de:0030-drops-255568},
  doi =		{10.4230/LIPIcs.STACS.2026.67},
  annote =	{Keywords: weighted automata, cost register automata, ambiguity, linear recurrence sequences, equivalence problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.53
Maximum Reachability Orientation of Mixed Graphs

Authors: Florian Hörsch

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

Abstract
We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph D, we use P(D) for the set of ordered pairs of distinct vertices in V(D) and we define κ_D:P(D) → {0,1} by κ_D(u,v) = 1 if v is reachable from u in D, and κ_D(u,v) = 0, otherwise. We use R(D) = ∑_{(u,v) ∈ P(D)}κ_D(u,v). Now, given a mixed graph G, we aim to find an orientation x⃑{G} of G that maximizes R(x⃑{G}). Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs. We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard. We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number k of preoriented arcs of G, a poorly studied form of parameterization. We show that the problem can be solved in time n^{O(k)} and that a (1-ε)-approximation can be computed in time f(k,ε)n^{O(1)} for any ε > 0.
Cite as

Florian Hörsch. Maximum Reachability Orientation of Mixed Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{horsch:LIPIcs.STACS.2026.53,
  author =	{H\"{o}rsch, Florian},
  title =	{{Maximum Reachability Orientation of Mixed Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{53:1--53: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.53},
  URN =		{urn:nbn:de:0030-drops-255421},
  doi =		{10.4230/LIPIcs.STACS.2026.53},
  annote =	{Keywords: orientations, mixed graphs, reachability, parameterized complexity, approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.59
When Is Local Search Both Effective and Efficient?

Authors: Artem Kaznatcheev and Sofia Vazquez Alferez

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

Abstract
Combinatorial optimization problems implicitly define fitness landscapes that combine the numeric structure of the "fitness" function to be maximized with the combinatorial structure of which assignments are "adjacent". Local search starts at an assignment in this landscape and successively moves assignments until no further improvement is possible among the adjacent assignments. Classic analyses of local search algorithms have focused more on the question of effectiveness ("did we find a good solution?") and often implicitly assumed that there are no doubts about their efficiency ("did we find it quickly?"). But there are many reasons to doubt the efficiency of local search. Even if we focus on fitness landscapes on the hypercube that are single peaked on every subcube (known as semismooth fitness landscapes, completely unimodal pseudo-Boolean functions, or acyclic unique sink orientations) where effectiveness is obvious, many local search algorithms are known to be inefficient. Since fitness landscapes are unwieldy exponentially large objects, we focus on their polynomial-sized representations by instances of valued constraint satisfaction problems (VCSP). We define a "direction" for valued constraints such that directed VCSPs generate semismooth fitness landscapes. We call directed VCSPs oriented if they do not have any pair of variables with arcs in both directions. Since recognizing if a VCSP-instance is directed or oriented is coNP-complete, we generalized oriented VCSPs as conditionally-smooth fitness landscapes where the structural property of "conditionally-smooth" is recognizable in polynomial time for a VCSP-instance. We prove that many popular local search algorithms like random ascent, simulated annealing, history-based rules, jumping rules, and the Kernighan-Lin heuristic are very efficient on conditionally-smooth landscapes. But conditionally-smooth landscapes are still expressive enough so that other well-regarded local search algorithms like steepest ascent and random facet require a super-polynomial number of steps to find the fitness peak.
Cite as

Artem Kaznatcheev and Sofia Vazquez Alferez. When Is Local Search Both Effective and Efficient?. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaznatcheev_et_al:LIPIcs.STACS.2026.59,
  author =	{Kaznatcheev, Artem and Vazquez Alferez, Sofia},
  title =	{{When Is Local Search Both Effective and Efficient?}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{59:1--59:19},
  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.59},
  URN =		{urn:nbn:de:0030-drops-255480},
  doi =		{10.4230/LIPIcs.STACS.2026.59},
  annote =	{Keywords: valued constraint satisfaction problem, local search, algorithm analysis, constraint graphs, pseudo-Boolean functions, parameterized complexity}
}
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.50
On the PTAS Complexity of Multidimensional Knapsack

Authors: Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi

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

Abstract
We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A polynomial-time approximation scheme (PTAS) with running time n^{Θ(d/{ε})} has long been known for this problem, where {ε} is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O(n^{⌈ d/{ε} ⌉ - d}). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^{o(d/({ε)})}-time PTAS for larger values of d. In this work, we show that the running times of the best-known PTAS cannot be improved up to a polylogarithmic factor assuming the Exponential Time Hypothesis (ETH). Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions. Then, using a recent result of [Bafna Karthik and Minzer, STOC'25], we succeed in exhibiting tight trade-off between d and {ε} for all regimes of the parameters assuming d is sufficiently large. Informally, our result also shows that under ETH, for any function f there is no f(d/({ε)}) ⋅ n^{õ(d/({ε)})}-time (1-{ε})-approximation for d-dimensional knapsack, where n is the number of items and õ hides polylogarithmic factors in d/({ε)}.
Cite as

Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi. On the PTAS Complexity of Multidimensional Knapsack. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ITCS.2026.50,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Manurangsi, Pasin},
  title =	{{On the PTAS Complexity of Multidimensional Knapsack}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{50:1--50:22},
  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.50},
  URN =		{urn:nbn:de:0030-drops-253377},
  doi =		{10.4230/LIPIcs.ITCS.2026.50},
  annote =	{Keywords: d-dimensional Knapsack, Multidimensional Knapsack, PTAS, CSP}
}
  • Refine by Type
  • 234 Document/PDF
  • 152 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 19 2026
  • 134 2025
  • 3 2024
  • 1 2023
  • 5 2022
  • Show More...

  • Refine by Author
  • 35 Pilipczuk, Marcin
  • 16 Saurabh, Saket
  • 11 Fomin, Fedor V.
  • 9 Golovach, Petr A.
  • 9 Pilipczuk, Michal
  • Show More...

  • Refine by Series/Journal
  • 234 LIPIcs

  • Refine by Classification
  • 80 Theory of computation → Parameterized complexity and exact algorithms
  • 47 Theory of computation → Graph algorithms analysis
  • 43 Theory of computation → Fixed parameter tractability
  • 38 Mathematics of computing → Graph algorithms
  • 17 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 27 parameterized complexity
  • 15 Parameterized Complexity
  • 15 Treewidth
  • 12 treewidth
  • 11 fixed-parameter tractability
  • 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