94 Search Results for "Dell, Holger"

Volume

LIPIcs, Volume 249

17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

IPEC 2022, September 7-9, 2022, Potsdam, Germany

Editors: Holger Dell and Jesper Nederlof

Document
DOI: 10.4230/LIPIcs.STACS.2026.25
Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing

Authors: Marek Černý and Tim Seppelt

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

Abstract
Two graphs G and H are homomorphism indistinguishable over a graph class ℱ if they admit the same number of homomorphisms from every graph F ∈ ℱ. Many graph isomorphism relaxations such as (quantum) isomorphism and cospectrality can be characterised as homomorphism indistinguishability over specific graph classes. Thereby, the problems HomInd(ℱ) of deciding homomorphism indistinguishability over ℱ subsume diverse graph isomorphism relaxations whose complexities range from logspace to undecidable. Establishing the first general result on the complexity of HomInd(ℱ), Seppelt (MFCS 2024) showed that HomInd(ℱ) is in randomised polynomial time for every graph class ℱ of bounded treewidth that can be defined in counting monadic second-order logic CMSO₂. We show that this algorithm is conditionally optimal, i.e. it cannot be derandomised unless polynomial identity testing is in P. For CMSO₂-definable graph classes ℱ of bounded pathwidth, we improve the previous complexity upper bound for HomInd(ℱ) from P to C_ = L and show that this is tight. Secondarily, we establish a connection between homomorphism indistinguishability and multiplicity automata equivalence which allows us to pinpoint the complexity of the latter problem as C_ = L-complete.
Cite as

Marek Černý and Tim Seppelt. Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cerny_et_al:LIPIcs.STACS.2026.25,
  author =	{\v{C}ern\'{y}, Marek and Seppelt, Tim},
  title =	{{Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-255144},
  doi =		{10.4230/LIPIcs.STACS.2026.25},
  annote =	{Keywords: treewidth, Courcelle’s theorem, logspace, multiplicity automata, polynomial identity testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.46
Symmetric Algebraic Circuits and Homomorphism Polynomials

Authors: Anuj Dawar, Benedikt Pago, and Tim Seppelt

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

Abstract
The central open question of algebraic complexity is whether VP ≠ VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020), who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.
Cite as

Anuj Dawar, Benedikt Pago, and Tim Seppelt. Symmetric Algebraic Circuits and Homomorphism Polynomials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ITCS.2026.46,
  author =	{Dawar, Anuj and Pago, Benedikt and Seppelt, Tim},
  title =	{{Symmetric Algebraic Circuits and Homomorphism Polynomials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{46:1--46:15},
  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.46},
  URN =		{urn:nbn:de:0030-drops-253330},
  doi =		{10.4230/LIPIcs.ITCS.2026.46},
  annote =	{Keywords: algebraic complexity, finite model theory, symmetric circuits, homomorphism counting, graph homomorphism, treewidth, counting width, first-order logic with counting quantifiers}
}
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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.66
A Parameterized-Complexity Framework for Finding Local Optima

Authors: Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz

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

Abstract
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood. The traditional frameworks, PLS and the standard algorithm problem, introduced by Johnson, Papadimitriou, and Yannakakis (1988) fail to capture the methodology of local search algorithms: PLS is concerned with finding a local optimum and not with using local search, while the standard algorithm problem restricts each improvement step to follow a fixed pivoting rule. In this work, we introduce a novel formulation of local search which provides a middle ground between these models. In particular, the task is to output not only a local optimum but also a chain of local improvements leading to it. With this framework, we aim to capture the challenge in designing a good pivoting rule. Especially, when combined with the parameterized complexity paradigm, it enables both strong lower bounds and meaningful tractability results. Unlike previous works that combined parameterized complexity with local search, our framework targets the whole task of finding a local optimum and not only a single improvement step. Focusing on two representative meta-problems - Subset Weight Optimization Problem with the c-swap neighborhood and Weighted Circuit with the flip neighborhood - we establish fixed-parameter tractability results related to the number of distinct weights, while ruling out an analogous result when parameterizing by the distance to the nearest optimum via a new type of reduction.
Cite as

Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz. A Parameterized-Complexity Framework for Finding Local Optima. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ITCS.2026.66,
  author =	{Ganian, Robert and Hoang, Hung P. and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Parameterized-Complexity Framework for Finding Local Optima}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{66:1--66:20},
  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.66},
  URN =		{urn:nbn:de:0030-drops-253532},
  doi =		{10.4230/LIPIcs.ITCS.2026.66},
  annote =	{Keywords: Local Search, Parameterized Complexity, PLS}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.32
Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Authors: Jin-Yi Cai and Ben Young

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

Abstract
Valiant’s Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets ℱ and 𝒢 of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then ℱ and 𝒢 are Holant-indistinguishable, i.e., every tensor network using tensors from ℱ, respectively from 𝒢, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable ℱ and 𝒢 always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GL_q-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class TOCI introduced by Lysikov and Walter [Vladimir Lysikov and Michael Walter, 2024], and hence hard for graph isomorphism.
Cite as

Jin-Yi Cai and Ben Young. Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2026.32,
  author =	{Cai, Jin-Yi and Young, Ben},
  title =	{{Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-253198},
  doi =		{10.4230/LIPIcs.ITCS.2026.32},
  annote =	{Keywords: Holant, Orbit Closure Intersection, Homomorphism Indistinguishability, Tensor Network}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

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

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.19
Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

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

Abstract
Recently, Bojikian and Kratsch [ICALP 2024] presented a novel approach to tackle connectivity problems parameterized by clique-width (cw), based on counting (modulo 2) the number of representations of partial solutions, while allowing for possibly multiple representations to exist for the same partial solution. Using this technique, they got a SETH-tight bound of 𝒪^*(3^{cw}) for the Steiner Tree problem, which was left open by Hegerfeld and Kratsch [ESA 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time 𝒪^*(12^{cw}). Moreover, we prove that our result is tight by providing a SETH-based lower bound excluding algorithms with running time 𝒪^*((12-ε)^{cw}). This answers another question of Hegerfeld and Kratsch [ESA 2023].
Cite as

Narek Bojikian and Stefan Kratsch. Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.IPEC.2025.19,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{19:1--19:15},
  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.19},
  URN =		{urn:nbn:de:0030-drops-251516},
  doi =		{10.4230/LIPIcs.IPEC.2025.19},
  annote =	{Keywords: Parameterized complexity, connected odd cycle transversal, clique-width}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.20
Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

Authors: Jonne Visser and Hans L. Bodlaender

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

Abstract
In this paper, we give new and faster deterministic algorithms to count the number of k-paths and trees in host graphs of bounded treewidth. Our algorithms use time that is single-exponential in the treewidth, and employ the determinant method from [Hans L. Bodlaender et al., 2015]. Modifications of the algorithms count in single-exponential time the number of k-paths between specified end-points, the number of k-cycles, and the number of trees with k vertices that are a subgraph of the host graph.
Cite as

Jonne Visser and Hans L. Bodlaender. Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{visser_et_al:LIPIcs.IPEC.2025.20,
  author =	{Visser, Jonne and Bodlaender, Hans L.},
  title =	{{Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{20:1--20:14},
  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.20},
  URN =		{urn:nbn:de:0030-drops-251529},
  doi =		{10.4230/LIPIcs.IPEC.2025.20},
  annote =	{Keywords: Parameterized Complexity, Counting Subgraphs, #k-path, Dynamic Programming, Tree Decomposition, Determinant Method}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.23
Enumeration Kernels for Vertex Cover and Feedback Vertex Set

Authors: Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau

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

Abstract
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creignou et al. [Theory Comput. Syst., 2017], and development in the area has started to accelerate with the work of Golovach et al. [J. Comput. Syst. Sci., 2022]. The latter introduced polynomial-delay enumeration kernels and applied them in the study of structural parameterizations of the Matching Cut problem and some variants. Few other results, mostly on Longest Path and some generalizations of Matching Cut, have also been developed. However, little success has been seen in enumeration versions of Vertex Cover and Feedback Vertex Set, some of the most studied problems in kernelization. In this paper, we address this shortcoming. Our first result is a polynomial-delay enumeration kernel with 2k vertices for Enum Vertex Cover, where we wish to list all solutions with at most k vertices. This is obtained by developing a non-trivial lifting algorithm for the classical crown decomposition reduction rule, and directly improves upon the kernel with 𝒪(k²) vertices derived from the work of Creignou et al. Our other result is a polynomial-delay enumeration kernel with 𝒪(k³) vertices and edges for Enum Feedback Vertex Set; the proof is inspired by some ideas of Thomassé [TALG, 2010], but with a weaker bound on the kernel size due to difficulties in applying the q-expansion technique.
Cite as

Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau. Enumeration Kernels for Vertex Cover and Feedback Vertex Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.IPEC.2025.23,
  author =	{Bougeret, Marin and C. M. Gomes, Guilherme and dos Santos, Vinicius F. and Sau, Ignasi},
  title =	{{Enumeration Kernels for Vertex Cover and Feedback Vertex Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{23:1--23:18},
  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.23},
  URN =		{urn:nbn:de:0030-drops-251552},
  doi =		{10.4230/LIPIcs.IPEC.2025.23},
  annote =	{Keywords: Kernelization, Enumeration, Vertex cover, Crown decomposition, Feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

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

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.31
Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard

Authors: Benjamin Bergougnoux and Lars Jaffke

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

Abstract
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.
Cite as

Benjamin Bergougnoux and Lars Jaffke. Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 31:1-31:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.IPEC.2025.31,
  author =	{Bergougnoux, Benjamin and Jaffke, Lars},
  title =	{{Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{31:1--31:10},
  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.31},
  URN =		{urn:nbn:de:0030-drops-251631},
  doi =		{10.4230/LIPIcs.IPEC.2025.31},
  annote =	{Keywords: Hamiltonian Path, Hamiltonian Cycle, Mim-Width, Para-NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.96
Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

Authors: Radu Curticapean, Simon Döring, and Daniel Neuen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the parameterized problem #IndSub(Φ) for fixed graph properties Φ, given as input a graph G and an integer k, the task is to compute the number of induced k-vertex subgraphs satisfying Φ. Dörfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that #IndSub(Φ) is #W[1]-hard for all non-meager properties Φ, i.e., properties that are nontrivial for infinitely many k. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024]. We refute this conjecture by showing that induced k-vertex graphs that are scorpions can be counted in time O(n⁴) for all k. Scorpions were introduced more than 50 years ago in the context of the evasiveness conjecture. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH. Moreover, we formulate an updated conjecture on the complexity of #IndSub(Φ) that correctly captures the complexity status of scorpions and related constructions.
Cite as

Radu Curticapean, Simon Döring, and Daniel Neuen. Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 96:1-96:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.ESA.2025.96,
  author =	{Curticapean, Radu and D\"{o}ring, Simon and Neuen, Daniel},
  title =	{{Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{96:1--96:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.96},
  URN =		{urn:nbn:de:0030-drops-245651},
  doi =		{10.4230/LIPIcs.ESA.2025.96},
  annote =	{Keywords: induced subgraphs, counting complexity, parameterized complexity, scorpions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.16
On Algorithmic Applications of ℱ-Branchwidth

Authors: Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, and Paloma T. Lima

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
F-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In this work, we search for algorithmic applications of F-branchwidth measures that do not have an equivalent counterpart in the literature so far. Our first contribution is a minimal set of eleven F-branchwidth measures such that each of the infinitely many F-branchwidth measures is equivalent to one of the eleven. We observe that for the FO Model Checking problem, each F-branchwidth is either equivalent to clique-width (and therefore has an FPT-algorithm by formula length plus the width) or the problem remains as hard as on general graphs even on graphs of constant width. Next, we study the number of equivalence classes of the neighborhood equivalence in a decomposition, which upper bounds the run time of the model checking algorithm for ACDN logic recently introduced by Bergougnoux et al. [SODA 2023]. We give structural lower bounds that show that for each F-branchwidth, an efficient model checking algorithm was already known or cannot be obtained via this method. Lastly, we classify the complexity of Independent Set parameterized by any F-branchwidth except for one open case. Also here, our contributions are lower bounds. In this context, we also prove that Independent Set on graphs of mim-width w cannot be solved in time n^o(w) unless the Exponential Time Hypothesis fails, answering an open question in the literature.
Cite as

Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, and Paloma T. Lima. On Algorithmic Applications of ℱ-Branchwidth. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2025.16,
  author =	{Bergougnoux, Benjamin and Hamm, Thekla and Jaffke, Lars and Lima, Paloma T.},
  title =	{{On Algorithmic Applications of ℱ-Branchwidth}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.16},
  URN =		{urn:nbn:de:0030-drops-244849},
  doi =		{10.4230/LIPIcs.ESA.2025.16},
  annote =	{Keywords: Graph width parameters, parameterized complexity, F-branchwidth, tree-width, clique-width, rank-width, mim-width, FO model checking, DN logic, Independent Set, ETH}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.110
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

Authors: László Kozma and Junqi Tan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
For many hard computational problems, simple algorithms that run in time 2ⁿ ⋅ n^O(1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this paper we obtain algorithms with running time O(1.9999977ⁿ) on input graphs with n vertices, for the following well-studied problems: - d-Cut: find a proper cut in which no vertex has more than d neighbors on the other side of the cut; - Internal Partition: find a proper cut in which every vertex has at least as many neighbors on its side of the cut as on the other side; and - (α,β)-Domination: given intervals α,β ⊆ [0,n], find a subset S of the vertices, so that for every vertex v ∈ S the number of neighbors of v in S is from α and for every vertex v ∉ S, the number of neighbors of v in S is from β. Our algorithms are exceedingly simple, combining the split and list technique (Horowitz and Sahni, 1974; Williams, 2005) with a tool from computational geometry: orthogonal range searching in the moderate dimensional regime (Chan, 2017). Our technique is applicable to the decision, optimization and counting versions of these problems and easily extends to various generalizations with more fine-grained, vertex-specific constraints, as well as to directed, balanced, and other variants. Algorithms with running times of the form cⁿ, for c < 2, were known for the first problem only for constant d, and for the third problem for certain special cases of α and β; for the second problem we are not aware of such results.
Cite as

László Kozma and Junqi Tan. Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 110:1-110:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2025.110,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Faster Exponential Algorithms for Cut Problems via Geometric Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{110:1--110:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.110},
  URN =		{urn:nbn:de:0030-drops-245796},
  doi =		{10.4230/LIPIcs.ESA.2025.110},
  annote =	{Keywords: graph algorithms, cuts, exponential time, data structures}
}
  • Refine by Type
  • 93 Document/PDF
  • 35 Document/HTML
  • 1 Volume

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

  • Refine by Author
  • 16 Dell, Holger
  • 8 Curticapean, Radu
  • 8 Roth, Marc
  • 4 Bodlaender, Hans L.
  • 4 Fomin, Fedor V.
  • Show More...

  • Refine by Series/Journal
  • 91 LIPIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 34 Theory of computation → Parameterized complexity and exact algorithms
  • 17 Theory of computation → Graph algorithms analysis
  • 16 Theory of computation → Problems, reductions and completeness
  • 13 Mathematics of computing → Graph algorithms
  • 12 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 14 parameterized complexity
  • 8 Parameterized Complexity
  • 6 counting complexity
  • 6 treewidth
  • 5 FPT
  • 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