12 Search Results for "van Bevern, René"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.7
An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem

Authors: Marco Aldi, Sevag Gharibian, and Dorian Rudolph

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

Abstract
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on Bézout’s theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA ⊆ MHS.
Cite as

Marco Aldi, Sevag Gharibian, and Dorian Rudolph. An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aldi_et_al:LIPIcs.ITCS.2026.7,
  author =	{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian},
  title =	{{An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{7:1--7:24},
  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.7},
  URN =		{urn:nbn:de:0030-drops-252946},
  doi =		{10.4230/LIPIcs.ITCS.2026.7},
  annote =	{Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), Quantum Satisfiability Problem (QSAT), total function NP (TFNP)}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.4
On the Complexity of Secluded Path Problems

Authors: Tesshu Hanaka and Daisuke Tsuru

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

Abstract
This paper investigates the complexity of finding secluded paths in graphs. We focus on the Short Secluded Path problem and a natural new variant we introduce, Shortest Secluded Path. Formally, given an undirected graph G = (V, E), two vertices s,t ∈ V, and two integers k,l, the Short Secluded Path problem asks whether there exists an s-t path of length at most k with at most l neighbors. This problem is known to be computationally hard: it is W[1]-hard when parameterized by the path length k or by cliquewidth, and para-NP-complete when parameterized by the number l of neighbors. The fixed-parameter tractability is known for k+l or treewidth. In this paper, we expand the parameterized complexity landscape by designing (1) an XP algorithm parameterized by cliquewidth and (2) fixed-parameter algorithms parameterized by neighborhood diversity and twin cover number, respectively. As a byproduct, our results also provide parameterized algorithms for the classic s-t k-Path problem. Furthermore, we introduce the Shortest Secluded Path problem, which seeks a shortest s-t path with the minimum number of neighbors. In contrast to the hardness of the original problem, we reveal that this variant is solvable in polynomial time on unweighted graphs. We complete this by showing that for edge-weighted graphs, the problem becomes W[1]-hard yet remains in XP when parameterized by the shortest path distance between s and t.
Cite as

Tesshu Hanaka and Daisuke Tsuru. On the Complexity of Secluded Path Problems. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.IPEC.2025.4,
  author =	{Hanaka, Tesshu and Tsuru, Daisuke},
  title =	{{On the Complexity of Secluded Path Problems}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{4:1--4:16},
  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.4},
  URN =		{urn:nbn:de:0030-drops-251361},
  doi =		{10.4230/LIPIcs.IPEC.2025.4},
  annote =	{Keywords: Secluded path, Parameterized complexity, Polynomial-time algorithm}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.7
Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints

Authors: Christina Büsing, Maurice Draeger, and Corinna Mathwieser

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

Abstract
We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the sum of completion times (P|gen-prec, p_j = 1|γ, γ ∈ {C_max,∑_jC_j}). In our setting, each job is equipped with a Boolean formula (precedence constraint) over the set of jobs. A schedule satisfies a job’s precedence constraint if setting earlier jobs to true satisfies the formula. Our definition generalizes several common types of precedence constraints: classical and-constraints if every formula is a conjunction, or-constraints if every formula is a disjunction, and and/or-constraints if every formula is in conjunctive normal form. We prove fixed-parameter tractability when parameterizing by the number of predecessors. For parameterization by the number of successors, however, the complexity depends on the structure of the precedence constraints. If every constraint is a conjunction or a disjunction, we prove the problem to be fixed-parameter tractable. For constraints in disjunctive normal form, we prove W[1]-hardness. We show that the and/or-constrained problem is NP-hard, even for a single successor. Moreover, we prove NP-hardness on two machines if every constraint is a conjunction or a disjunction. This result not only proves para-NP-hardness for parameterization by the number of machines but also complements the polynomial-time solvability on two machines if every constraint is a conjunction [Coffman and Graham, 1972] or if every constraint is a disjunction [Johannes, 2005].
Cite as

Christina Büsing, Maurice Draeger, and Corinna Mathwieser. Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{busing_et_al:LIPIcs.IPEC.2025.7,
  author =	{B\"{u}sing, Christina and Draeger, Maurice and Mathwieser, Corinna},
  title =	{{Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{7:1--7:16},
  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.7},
  URN =		{urn:nbn:de:0030-drops-251390},
  doi =		{10.4230/LIPIcs.IPEC.2025.7},
  annote =	{Keywords: scheduling, precedence constraints, fixed-parameter tractability, complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.53
A Parameterized Study of Secluded Structures in Directed Graphs

Authors: Jonas Schmidt, Shaily Verma, and Nadym Mallek

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Given an undirected graph G and an integer k, the Secluded Π-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property Π and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problems in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems {In, Out, Total}-Secluded Π-Subgraph, where given a directed graph G and an integer k, we want to find an induced subgraph satisfying Π of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties Π. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the Out-Secluded ℱ-Free Subgraph problem with parameter k is W[1]-hard, where ℱ is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded α-Bounded Subgraph when parameterized by k, where α-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^k n^𝒪(1).
Cite as

Jonas Schmidt, Shaily Verma, and Nadym Mallek. A Parameterized Study of Secluded Structures in Directed Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.ISAAC.2025.53,
  author =	{Schmidt, Jonas and Verma, Shaily and Mallek, Nadym},
  title =	{{A Parameterized Study of Secluded Structures in Directed Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.53},
  URN =		{urn:nbn:de:0030-drops-249616},
  doi =		{10.4230/LIPIcs.ISAAC.2025.53},
  annote =	{Keywords: Secluded Subgraph, Parametrized Complexity, Directed Graphs, Strong Connectivity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.90
Elimination Distance to Dominated Clusters

Authors: Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In the Dominated Cluster Deletion problem, we are given an undirected graph G and integers k and d and the question is to decide whether there exists a set of at most k vertices whose removal results in a graph in which each connected component has a dominating set of size at most d. In the Elimination Distance to Dominated Clusters problem, we are again given an undirected graph G and integers k and d and the question is to decide whether we can recursively delete vertices up to depth k such that each remaining connected component has a dominating set of size at most d. Bentert et al. [Bentert et al., MFCS 2024] recently provided an almost complete classification of the parameterized complexity of Dominated Cluster Deletion with respect to the parameters k, d, c, and Δ, where c and Δ are the degeneracy, and the maximum degree of the input graph, respectively. In particular, they provided a non-uniform algorithm with running time f(k,d)⋅ n^{𝒪(d)}. They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter k + d + c. We provide a uniform algorithm running in time f(k,d)⋅ n^{𝒪(d)} for both Dominated Cluster Deletion and Elimination Distance to Dominated Clusters. We furthermore show that both problems are FPT when parameterized by k+d+𝓁, where 𝓁 is the semi-ladder index of the input graph, a parameter that is upper bounded and may be much smaller than the degeneracy c, positively answering the open question of Bentert et al. We further complete the picture by providing an almost full classification for the parameterized complexity and kernelization complexity of Elimination Distance to Dominated Clusters. The one difficult base case that remains open is whether Treedepth (the case d = 0) is NP-hard on graphs of bounded maximum degree.
Cite as

Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. Elimination Distance to Dominated Clusters. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schirrmacher_et_al:LIPIcs.MFCS.2025.90,
  author =	{Schirrmacher, Nicole and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Elimination Distance to Dominated Clusters}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.90},
  URN =		{urn:nbn:de:0030-drops-241978},
  doi =		{10.4230/LIPIcs.MFCS.2025.90},
  annote =	{Keywords: Graph theory, Fixed-parameter algorithms, Dominated cluster, Elimination distance}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.20
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components

Authors: Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Motivated by the growing interest in graph clustering and the framework proposed during the Dagstuhl Seminar 23331, we consider a natural specialization of this general approach (as also suggested during the seminar). The seminar introduced a broad perspective on clustering, where the goal is to partition a graph into connected components (or "clusters") that satisfy simple structural integrity constraints - not necessarily limited to cliques. In our work, we focus on the case where each cluster is required to have bounded vertex cover number. Specifically, a connected component C satisfies this condition if there exists a set S ⊆ V(C) with |S| ≤ d such that C - S is an independent set. We study this within the framework of the {Vertex Deletion to d-Vertex Cover Components} ({Vertex Deletion to d-VCC}) problem: given a graph G and an integer k, the task is to determine whether there exists a vertex set S ⊆ V(G) of size at most k such that every connected component of G - S has vertex cover number at most d. We also examine the edge-deletion variant, {Edge Deletion to d-Vertex Cover Components} ({Edge Deletion to d-VCC}), where the goal is to delete at most k edges so that each connected component of the resulting graph has vertex cover number at most d. We obtain following results. 1) {Vertex Deletion to d-VCC} admits a kernel with {𝒪}(d⁶k³) vertices and {𝒪}(d⁹k⁴) edges. 2) {Edge Deletion to d-VCC}, admits a kernel with {𝒪}(d⁴k) vertices and {𝒪}(d⁵k) edges. Both of our kernelization algorithms run in time 𝒪(1.253^d ⋅ (kd)^{𝒪(1)} ⋅ n log n). It is important to note that, unless the Exponential Time Hypothesis (ETH) fails, the dependence on d cannot be improved to 2^{o(d)}, as the case k = 0 reduces to solving the classical Vertex Cover problem, which is known to require 2^{Ω(d)} time under ETH. A key ingredient in our kernelization algorithms is a structural result about the hereditary graph class 𝒢_d, consisting of graphs in which every connected component has vertex cover number at most d. We show that 𝒢_d admits a finite obstruction set (with respect to the induced subgraph relation) of size 2^{𝒪(d²)}, where each obstruction graph has at most 3d + 2 vertices. This combinatorial result may be of independent interest.
Cite as

Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh. Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2025.20,
  author =	{Bhyravarapu, Sriram and Kumar, Pritesh and Kundu, Madhumita and Roy, Shivesh K. and Sahiba and Saurabh, Saket},
  title =	{{Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.20},
  URN =		{urn:nbn:de:0030-drops-241276},
  doi =		{10.4230/LIPIcs.MFCS.2025.20},
  annote =	{Keywords: Parameterized complexity, Polynomial Kernels, Vertex Cover, Finite Forbidden Characterization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.41
Residue Domination in Bounded-Treewidth Graphs

Authors: Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For the vertex selection problem (σ,ρ)-DomSet one is given two fixed sets σ and ρ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in σ and, for every unselected vertex, the number of selected neighbors is in ρ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when σ and ρ are two (potentially different) residue classes modulo m ≥ 2. We study the problem parameterized by treewidth and present an algorithm that solves in time m^tw ⋅ n^O(1) the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case m ≥ 3 not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no (m-ε)^pw ⋅ n^O(1)-time algorithm parameterized by pathwidth pw, unless SETH fails. For m = 2, we extend these bounds to the minimization version as the decision version is efficiently solvable.
Cite as

Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz. Residue Domination in Bounded-Treewidth Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.STACS.2025.41,
  author =	{Greilhuber, Jakob and Schepper, Philipp and Wellnitz, Philip},
  title =	{{Residue Domination in Bounded-Treewidth Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.41},
  URN =		{urn:nbn:de:0030-drops-228675},
  doi =		{10.4230/LIPIcs.STACS.2025.41},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Generalized Dominating Set, Strong Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.44
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Authors: Tim A. Hartmann and Dániel Marx

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these problems are well understood on bounded-treewidth graphs [Katsikarelis, Lampis, and Paschos, Discret. Appl. Math 2022][Borradaile and Le, IPEC 2016]: given a tree decomposition of width t, the two problems can be solved in time d^t⋅ n^O(1) and (2d+1)^t⋅ n^O(1), respectively. Furthermore, assuming the Strong Exponential-Time Hypothesis (SETH), the base constants are best possible in these running times: they cannot be improved to d-ε and 2d+1-ε, respectively, for any ε > 0. We investigate continuous versions of these problems in a setting introduced by Megiddo and Tamir [SICOMP 1983], where every edge is modeled by a unit-length interval of points. In the δ-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least δ from each other. Similarly, in the δ-Covering problem, the task is to find a minimum number of points (possibly inside edges) such that every point of the graph (including those inside edges) is at distance at most δ from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs. 1) Let δ = a/b with a and b being coprime. If a ≤ 2, then δ-Dispersion is polynomial-time solvable. For a ≥ 3, given a tree decomposition of width t, the problem can be solved in time (2a)^t⋅ n^O(1), and, assuming SETH, there is no (2a-ε)^t⋅n^{O(1)} time algorithm for any ε > 0. 2) Let δ = a/b with a and b being coprime. If a = 1, then δ-Covering is polynomial-time solvable. For a ≥ 2, given a tree decomposition of width t, the problem can be solved in time ((2+2(bod 2)) a)^t⋅ n^O(1), and, assuming SETH, there is no ((2+2(bod 2))a -ε)^t⋅n^O(1) time algorithm for any ε > 0. 3) For every fixed irrational number δ > 0 satisfying some mild computability condition, both δ-Dispersion and δ-Covering can be solved in time n^O(t) on graphs of treewidth t. We show a very explicitly defined irrational number δ = (4∑_{j=1}^∞ 2^{-2^j})^{-1} ≈ 0.790085 such that δ-Dispersion and δ/2-Covering are W[1]-hard parameterized by the treewidth t of the input graph, and, assuming ETH, cannot be solved in time f(t)⋅n^o(t). As a key step in obtaining these results, we extend earlier results on distance-d versions of Independent Set and Dominating Set: We determine the exact complexity of these problems in the special case when the input graph arises from some graph G' by subdividing every edge exactly b times.
Cite as

Tim A. Hartmann and Dániel Marx. Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.STACS.2025.44,
  author =	{Hartmann, Tim A. and Marx, D\'{a}niel},
  title =	{{Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.44},
  URN =		{urn:nbn:de:0030-drops-228700},
  doi =		{10.4230/LIPIcs.STACS.2025.44},
  annote =	{Keywords: Independence, Domination, Irrationals, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.47
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines

Authors: Klaus Heeger and Hendrik Molter

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this work, we study the computational (parameterized) complexity of P∣ r_j, p_j = p ∣∑ w_j U_j. Here, we are given m identical parallel machines and n jobs with equal processing time, each characterized by a release date, a due date, and a weight. The task is to find a feasible schedule, that is, an assignment of the jobs to starting times on machines, such that no job starts before its release date and no machine processes several jobs at the same time, that minimizes the weighted number of tardy jobs. A job is considered tardy if it finishes after its due date. Our main contribution is showing that P∣r_j, p_j = p∣∑ U_j (the unweighted version of the problem) is NP-hard and W[2]-hard when parameterized by the number of machines. The former resolves an open problem in Note 2.1.19 by Kravchenko and Werner [Journal of Scheduling, 2011] and Open Problem 2 by Sgall [ESA, 2012], and the latter resolves Open Problem 7 by Mnich and van Bevern [Computers & Operations Research, 2018]. Furthermore, our result shows that the known XP-algorithm by Baptiste et al. [4OR, 2004] for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of machines is optimal from a classification standpoint. On the algorithmic side, we provide alternative running time bounds for the above-mentioned known XP-algorithm. Our analysis shows that P∣r_j, p_j = p∣∑ w_j U_j is contained in XP when parameterized by the processing time, and that it is contained in FPT when parameterized by the combination of the number of machines and the processing time. Finally, we give an FPT-algorithm for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of release dates or the number of due dates. With this work, we lay out the foundation for a systematic study of the parameterized complexity of P∣r_j, p_j = p∣∑ w_j U_j.
Cite as

Klaus Heeger and Hendrik Molter. Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{heeger_et_al:LIPIcs.STACS.2025.47,
  author =	{Heeger, Klaus and Molter, Hendrik},
  title =	{{Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.47},
  URN =		{urn:nbn:de:0030-drops-228736},
  doi =		{10.4230/LIPIcs.STACS.2025.47},
  annote =	{Keywords: Scheduling, Identical Parallel Machines, Weighted Number of Tardy Jobs, Uniform Processing Times, Release Dates, NP-hard Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.10
Parameterized Algorithms and Data Reduction for Safe Convoy Routing

Authors: René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph G=(V,E), two vertices s,t in V, and two integers k,l, we search for a simple s-t-path with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2^O(tw) * l^2 * n-time algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.
Cite as

René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized Algorithms and Data Reduction for Safe Convoy Routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2018.10,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Tsidulko, Oxana Yu.},
  title =	{{Parameterized Algorithms and Data Reduction for Safe Convoy Routing}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{10:1--10:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.10},
  URN =		{urn:nbn:de:0030-drops-97157},
  doi =		{10.4230/OASIcs.ATMOS.2018.10},
  annote =	{Keywords: NP-hard problem, fixed-parameter tractability, problem kernelization, shortest path, secluded solution}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.5
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.
Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.130
Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems

Authors: René van Bevern, Christian Komusiewicz, and Manuel Sorge

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
We show that any alpha(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(alpha(C))-approximation algorithms for various mixed, windy, and capacitated arc routing problems. Herein, C is the number of weakly-connected components in the subgraph induced by the positive-demand arcs, a number that can be expected to be small in applications. In conjunction with known results, we derive constant-factor approximations if C is in O(log n) and O(log(C)/log(log(C)))-approximations in general.
Cite as

René van Bevern, Christian Komusiewicz, and Manuel Sorge. Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 130-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2015.130,
  author =	{van Bevern, Ren\'{e} and Komusiewicz, Christian and Sorge, Manuel},
  title =	{{Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{130--143},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.130},
  URN =		{urn:nbn:de:0030-drops-54575},
  doi =		{10.4230/OASIcs.ATMOS.2015.130},
  annote =	{Keywords: vehicle routing, transportation, Rural Postman, Chinese Postman, NP- hard problem, parameterized algorithm, combinatorial optimization}
}
  • Refine by Type
  • 12 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 8 2025
  • 1 2018
  • 1 2017
  • 1 2015

  • Refine by Author
  • 3 van Bevern, René
  • 2 Fluschnik, Till
  • 2 Molter, Hendrik
  • 2 Sorge, Manuel
  • 1 Aldi, Marco
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 4 Mathematics of computing → Graph algorithms
  • 1 Computing methodologies → Planning and scheduling
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 2 Parameterized complexity
  • 2 Treewidth
  • 2 fixed-parameter tractability
  • 1 Chinese Postman
  • 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