Volume
LIPIcs, Volume 285
18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Publication Details
- published at: 2023-12-13
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-305-8
- DBLP: db/conf/iwpec/ipec2023
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 285, IPEC 2023, Complete Volume
Abstract
LIPIcs, Volume 285, IPEC 2023, Complete Volume
Cite as
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@Proceedings{misra_et_al:LIPIcs.IPEC.2023,
title = {{LIPIcs, Volume 285, IPEC 2023, Complete Volume}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {1--644},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023},
URN = {urn:nbn:de:0030-drops-194183},
doi = {10.4230/LIPIcs.IPEC.2023},
annote = {Keywords: LIPIcs, Volume 285, IPEC 2023, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{misra_et_al:LIPIcs.IPEC.2023.0,
author = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {0:i--0:xviii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.0},
URN = {urn:nbn:de:0030-drops-194191},
doi = {10.4230/LIPIcs.IPEC.2023.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Kernelizing Temporal Exploration Problems
Abstract
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, where the agent’s task is to visit at least k vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L+k, L + γ, and k+γ. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner.
We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph p(𝒢) = ∑_{i=1}^L (|E(G_i)|) - |V(G)| + 1. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in p(𝒢)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k.
Cite as
Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.1,
author = {Arrighi, Emmanuel and Fomin, Fedor V. and Golovach, Petr A. and Wolf, Petra},
title = {{Kernelizing Temporal Exploration Problems}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {1:1--1:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.1},
URN = {urn:nbn:de:0030-drops-194201},
doi = {10.4230/LIPIcs.IPEC.2023.1},
annote = {Keywords: Temporal graph, temporal exploration, computational complexity, kernel}
}
Document
Cluster Editing with Overlapping Communities
Abstract
Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example, in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Another strong motivation comes from language networks where trying to cluster words with similar usage can be confounded by homonyms, that is, words with multiple meanings like "bat". The recently introduced operation of vertex splitting is one natural approach to incorporating such overlap into Cluster Editing. First used in the context of graph drawing, this operation allows a vertex v to be replaced by two vertices whose combined neighborhood is the neighborhood of v (and thus v can belong to more than one cluster). The problem of transforming a graph into a cluster graph using at most k edge additions, edge deletions, or vertex splits is called Cluster Editing with Vertex Splitting and is known to admit a polynomial kernel with respect to k and an O(9^{k²} + n + m)-time (parameterized) algorithm. However, it was not known whether the problem is NP-hard, a question which was originally asked by Abu-Khzam et al. [Combinatorial Optimization, 2018]. We answer this in the affirmative. We further give an improved algorithm running in O(2^{7klog k} + n + m) time.
Cite as
Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2,
author = {Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra},
title = {{Cluster Editing with Overlapping Communities}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {2:1--2:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2},
URN = {urn:nbn:de:0030-drops-194218},
doi = {10.4230/LIPIcs.IPEC.2023.2},
annote = {Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm}
}
Document
Existential Second-Order Logic over Graphs: Parameterized Complexity
Abstract
By Fagin’s Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quantifiers (eso formulas). Subsequent research refined this result, culminating in powerful theorems that characterize for each possible sequence of first-order quantifiers how difficult the described problem can be. We transfer this line of inquiry to the parameterized setting, where the size of the set quantified by the second-order quantifier is the parameter. Many natural parameterized problems can be described in this way using simple sequences of first-order quantifiers: For the clique or vertex cover problems, two universal first-order quantifiers suffice ("for all pairs of vertices ... must hold"); for the dominating set problem, a universal followed by an existential quantifier suffice ("for all vertices, there is a vertex such that ..."); and so on. We present a complete characterization that states for each possible sequence of first-order quantifiers how high the parameterized complexity of the described problems can be. The uncovered dividing line between quantifier sequences that lead to tractable versus intractable problems is distinct from that known from the classical setting, and it depends on whether the parameter is a lower bound on, an upper bound on, or equal to the size of the quantified set.
Cite as
Max Bannach, Florian Chudigiewitsch, and Till Tantau. Existential Second-Order Logic over Graphs: Parameterized Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bannach_et_al:LIPIcs.IPEC.2023.3,
author = {Bannach, Max and Chudigiewitsch, Florian and Tantau, Till},
title = {{Existential Second-Order Logic over Graphs: Parameterized Complexity}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.3},
URN = {urn:nbn:de:0030-drops-194224},
doi = {10.4230/LIPIcs.IPEC.2023.3},
annote = {Keywords: existential second-order logic, graph problems, parallel algorithms, fixed-parameter tractability, descriptive complexity}
}
Document
On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model
Abstract
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set S of safe edges and a set U of unsafe edges and the task is to find a set T of at most k edges such that T - {u} is connected and spans V for any unsafe edge u ∈ T. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.
Cite as
Matthias Bentert, Jannik Schestag, and Frank Sommer. On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bentert_et_al:LIPIcs.IPEC.2023.4,
author = {Bentert, Matthias and Schestag, Jannik and Sommer, Frank},
title = {{On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {4:1--4:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.4},
URN = {urn:nbn:de:0030-drops-194232},
doi = {10.4230/LIPIcs.IPEC.2023.4},
annote = {Keywords: Flexible graph connectivity, NP-hard problem, parameterized complexity, below-guarantee parameterization, treewidth}
}
Document
Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity
Abstract
We consider the question of polynomial kernelization of a generalization of the classical Vertex Cover problem parameterized by a parameter that is provably smaller than the solution size. In particular, we focus on the c-Component Order Connectivity problem (c-COC) where given an undirected graph G and a non-negative integer t, the objective is to test whether there exists a set S of size at most t such that every component of G-S contains at most c vertices. Such a set S is called a c-coc set. It is known that c-COC admits a kernel with {O}(ct) vertices. Observe that for c = 1, this corresponds to the Vertex Cover problem.
We study the c-Component Order Connectivity problem parameterized by the size of a d-coc set (c-COC/d-COC), where c,d ∈ ℕ with c ≤ d. In particular, the input is an undirected graph G, a positive integer t and a set M of at most k vertices of G, such that the size of each connected component in G - M is at most d. The question is to find a set S of vertices of size at most t, such that the size of each connected component in G - S is at most c. In this paper, we give a kernel for c-COC/d-COC with O(k^{d-c+1}) vertices and O(k^{d-c+2}) edges. Our result exhibits that the difference in d and c, and not their absolute values, determines the exact degree of the polynomial in the kernel size.
When c = d = 1, the c-COC/d-COC problem is exactly the Vertex Cover problem parameterized by the solution size, which has a kernel with O(k) vertices and O(k²) edges, and this is asymptotically tight [Dell & Melkebeek, JACM 2014]. We also show that the dependence of d-c in the exponent of the kernel size cannot be avoided under reasonable complexity assumptions.
Cite as
Sriram Bhyravarapu, Satyabrata Jana, Saket Saurabh, and Roohani Sharma. Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bhyravarapu_et_al:LIPIcs.IPEC.2023.5,
author = {Bhyravarapu, Sriram and Jana, Satyabrata and Saurabh, Saket and Sharma, Roohani},
title = {{Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {5:1--5:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.5},
URN = {urn:nbn:de:0030-drops-194241},
doi = {10.4230/LIPIcs.IPEC.2023.5},
annote = {Keywords: Kernelization, Component Order Connectivity, Vertex Cover, Structural Parameterizations}
}
Document
The Parameterised Complexity Of Integer Multicommodity Flow
Abstract
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters.
In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter.
Cite as
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen. The Parameterised Complexity Of Integer Multicommodity Flow. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.6,
author = {Bodlaender, Hans L. and Mannens, Isja and Oostveen, Jelle J. and Pandey, Sukanya and van Leeuwen, Erik Jan},
title = {{The Parameterised Complexity Of Integer Multicommodity Flow}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {6:1--6:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.6},
URN = {urn:nbn:de:0030-drops-194250},
doi = {10.4230/LIPIcs.IPEC.2023.6},
annote = {Keywords: multicommodity flow, parameterised complexity, XNLP-completeness, XALP-completeness}
}
Document
Treewidth Is NP-Complete on Cubic Graphs
Abstract
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.
Cite as
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. Treewidth Is NP-Complete on Cubic Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.7,
author = {Bodlaender, Hans L. and Bonnet, \'{E}douard and Jaffke, Lars and Knop, Du\v{s}an and Lima, Paloma T. and Milani\v{c}, Martin and Ordyniak, Sebastian and Pandey, Sukanya and Such\'{y}, Ond\v{r}ej},
title = {{Treewidth Is NP-Complete on Cubic Graphs}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {7:1--7:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7},
URN = {urn:nbn:de:0030-drops-194263},
doi = {10.4230/LIPIcs.IPEC.2023.7},
annote = {Keywords: Treewidth, cubic graphs, degree, NP-completeness}
}
Document
Stretch-Width
Abstract
We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polynomial subdivisions do not have bounded stretch-width. This leaves open the possibility of efficient algorithms for a broad fragment of problems within Monadic Second-Order (MSO) logic on graphs of bounded stretch-width. In this direction, we prove that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth. As a consequence, in classes of bounded stretch-width, Maximum Independent Set can be solved in subexponential time 2^{Õ(n^{8/9})} on n-vertex graphs, and, if further the maximum degree is bounded, Existential Counting Modal Logic [Pilipczuk '11] can be model-checked in polynomial time. We also give a polynomial-time O(OPT²)-approximation for the stretch-width of symmetric 0,1-matrices or ordered graphs.
Somewhat unexpectedly, we prove that exponential subdivisions of bounded-degree graphs have bounded stretch-width. This allows to complement the logarithmic upper bound of treewidth with a matching lower bound. We leave as open the existence of an efficient approximation algorithm for the stretch-width of unordered graphs, if the exponential subdivisions of all graphs have bounded stretch-width, and if graphs of bounded stretch-width have logarithmic clique-width (or rank-width).
Cite as
Édouard Bonnet and Julien Duron. Stretch-Width. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2023.8,
author = {Bonnet, \'{E}douard and Duron, Julien},
title = {{Stretch-Width}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {8:1--8:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.8},
URN = {urn:nbn:de:0030-drops-194279},
doi = {10.4230/LIPIcs.IPEC.2023.8},
annote = {Keywords: Contraction sequences, twin-width, clique-width, algorithms, algorithmic metatheorems}
}
Document
Minimum Separator Reconfiguration
Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.
Cite as
Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
author = {C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
title = {{Minimum Separator Reconfiguration}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {9:1--9:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9},
URN = {urn:nbn:de:0030-drops-194288},
doi = {10.4230/LIPIcs.IPEC.2023.9},
annote = {Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
Abstract
Given an undirected graph G and a multiset of k terminal pairs 𝒳, the Vertex-Disjoint Paths (VDP) and Edge-Disjoint Paths (EDP) problems ask whether G has k pairwise internally vertex-disjoint paths and k pairwise edge-disjoint paths, respectively, connecting every terminal pair in 𝒳. In this paper, we study the kernelization complexity of VDP and EDP on subclasses of chordal graphs. For VDP, we design a 4k vertex kernel on split graphs and an 𝒪(k²) vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For EDP, we first prove that the problem is NP-complete on complete graphs. Then, we design an 𝒪(k^{2.75}) vertex kernel for EDP on split graphs, and improve it to a 7k+1 vertex kernel on threshold graphs. Lastly, we provide an 𝒪(k²) vertex kernel for EDP on block graphs and a 2k+1 vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al. [Theory Comput. Syst., 2015].
Cite as
Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi. Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chaudhary_et_al:LIPIcs.IPEC.2023.10,
author = {Chaudhary, Juhi and Gahlawat, Harmender and W{\l}odarczyk, Michal and Zehavi, Meirav},
title = {{Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.10},
URN = {urn:nbn:de:0030-drops-194296},
doi = {10.4230/LIPIcs.IPEC.2023.10},
annote = {Keywords: Kernelization, Parameterized Complexity, Vertex-Disjoint Paths Problem, Edge-Disjoint Paths Problem}
}
Document
Parameterized Complexity Classification for Interval Constraints
Abstract
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most k constraints, where k is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen’s interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set A of 13 basic comparison relations such as "precedes" or "during" for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP(Γ) for all Γ ⊆ A. IA is sometimes extended with unions of the relations in A or first-order definable relations over A, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP(A) in general, we then consider (parameterized) approximation algorithms. We first show that MinCSP(A) cannot be polynomial-time approximated within any constant factor and continue by presenting a factor-2 fpt-approximation algorithm. Once again, this algorithm has its roots in flow augmentation.
Cite as
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, and Roohani Sharma. Parameterized Complexity Classification for Interval Constraints. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{dabrowski_et_al:LIPIcs.IPEC.2023.11,
author = {Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Pilipczuk, Marcin and Sharma, Roohani},
title = {{Parameterized Complexity Classification for Interval Constraints}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {11:1--11:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.11},
URN = {urn:nbn:de:0030-drops-194306},
doi = {10.4230/LIPIcs.IPEC.2023.11},
annote = {Keywords: (minimum) constraint satisfaction problem, Allen’s interval algebra, parameterized complexity, cut problems}
}
Document
An FPT Algorithm for Temporal Graph Untangling
Abstract
Several classical combinatorial problems have been considered and analysed on temporal graphs. Recently, a variant of Vertex Cover on temporal graphs, called MinTimelineCover, has been introduced to summarize timeline activities in social networks. The problem asks to cover every temporal edge while minimizing the total span of the vertices (where the span of a vertex is the length of the timestamp interval it must remain active in). While the problem has been shown to be NP-hard even in very restricted cases, its parameterized complexity has not been fully understood. The problem is known to be in FPT under the span parameter only for graphs with two timestamps, but the parameterized complexity for the general case is open. We settle this open problem by giving an FPT algorithm that is based on a combination of iterative compression and a reduction to the Digraph Pair Cut problem, a powerful problem that has received significant attention recently.
Cite as
Riccardo Dondi and Manuel Lafond. An FPT Algorithm for Temporal Graph Untangling. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{dondi_et_al:LIPIcs.IPEC.2023.12,
author = {Dondi, Riccardo and Lafond, Manuel},
title = {{An FPT Algorithm for Temporal Graph Untangling}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.12},
URN = {urn:nbn:de:0030-drops-194311},
doi = {10.4230/LIPIcs.IPEC.2023.12},
annote = {Keywords: Temporal Graphs, Vertex Cover, Graph Algorithms, Parameterized Complexity}
}
Document
Budgeted Matroid Maximization: a Parameterized Viewpoint
Abstract
We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an 𝓁-matchoid ℳ on a ground set E, a profit function p:E → ℝ_{≥ 0}, a cost function c:E → ℝ_{≥ 0}, and a budget B ∈ ℝ_{≥ 0}, the goal is to find in the 𝓁-matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≤ B. The budgeted 𝓁-matchoid (BM) problem includes as special cases budgeted 𝓁-dimensional matching and budgeted 𝓁-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted 𝓁-dimensional matching (i.e., B = ∞) already for 𝓁 = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity.
We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for 𝓁-dimensional matching and budgeted 𝓁-matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.
Cite as
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted Matroid Maximization: a Parameterized Viewpoint. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{doronarad_et_al:LIPIcs.IPEC.2023.13,
author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
title = {{Budgeted Matroid Maximization: a Parameterized Viewpoint}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {13:1--13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.13},
URN = {urn:nbn:de:0030-drops-194329},
doi = {10.4230/LIPIcs.IPEC.2023.13},
annote = {Keywords: budgeted matching, budgeted matroid intersection, knapsack problems, FPT-approximation scheme}
}
Document
Computing Complexity Measures of Degenerate Graphs
Abstract
We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time O(d2^dn), afterwards queries can be computed efficiently using fast Möbius inversion.
This data structure turns out to be useful for a range of tasks, especially for finding bipartite patterns in degenerate graphs, and we outline an efficient algorithm for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(n^c), where c is a parameter of the pattern we call its left covering number.
Concrete applications of this algorithm include counting the number of (non-induced) bicliques in linear time, the number of co-matchings in quadratic time, as well as a constant-factor approximation of the ladder index in linear time.
Finally, we supplement our theoretical results with several implementations and run experiments on more than 200 real-world datasets - the largest of which has 8 million edges - where we obtain interesting insights into the VC-dimension of real-world networks.
Cite as
Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing Complexity Measures of Degenerate Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{drange_et_al:LIPIcs.IPEC.2023.14,
author = {Drange, P\r{a}l Gr{\o}n\r{a}s and Greaves, Patrick and Muzi, Irene and Reidl, Felix},
title = {{Computing Complexity Measures of Degenerate Graphs}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {14:1--14:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14},
URN = {urn:nbn:de:0030-drops-194333},
doi = {10.4230/LIPIcs.IPEC.2023.14},
annote = {Keywords: vc-dimension, datastructure, degeneracy, enumerating}
}
Document
An Improved Kernelization Algorithm for Trivially Perfect Editing
Abstract
In the Trivially Perfect Editing problem one is given an undirected graph G = (V,E) and an integer k and seeks to add or delete at most k edges in G to obtain a trivially perfect graph. In a recent work, Dumas et al. [Dumas et al., 2023] proved that this problem admits a kernel with O(k³) vertices. This result heavily relies on the fact that the size of trivially perfect modules can be bounded by O(k²) as shown by Drange and Pilipczuk [Drange and Pilipczuk, 2018]. To obtain their cubic vertex-kernel, Dumas et al. [Dumas et al., 2023] then showed that a more intricate structure, so-called comb, can be reduced to O(k²) vertices. In this work we show that the bound can be improved to O(k) for both aforementioned structures and thus obtain a kernel with O(k²) vertices. Our approach relies on the straightforward yet powerful observation that any large enough structure contains unaffected vertices whose neighborhood remains unchanged by an editing of size k, implying strong structural properties.
Cite as
Maël Dumas and Anthony Perez. An Improved Kernelization Algorithm for Trivially Perfect Editing. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{dumas_et_al:LIPIcs.IPEC.2023.15,
author = {Dumas, Ma\"{e}l and Perez, Anthony},
title = {{An Improved Kernelization Algorithm for Trivially Perfect Editing}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.15},
URN = {urn:nbn:de:0030-drops-194340},
doi = {10.4230/LIPIcs.IPEC.2023.15},
annote = {Keywords: Parameterized complexity, kernelization algorithms, graph modification, trivially perfect graphs}
}
Document
From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Abstract
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as classical graph problems on induced subgraphs of powers of partially-defined hypercubes.
In this paper, we follow up on this recent direction by investigating the Independent Set problem on this graph class, which has been studied in the data science setting under the name Diversity. We obtain a comprehensive picture of the problem’s parameterized complexity and establish its fixed-parameter tractability w.r.t. the solution size plus the power of the hypercube.
Given that several such FO-definable problems have been shown to be fixed-parameter tractable on the considered graph class, one may ask whether fixed-parameter tractability could be extended to capture all FO-definable problems. We answer this question in the negative by showing that FO model checking on induced subgraphs of hypercubes is as difficult as FO model checking on general graphs.
Cite as
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{eiben_et_al:LIPIcs.IPEC.2023.16,
author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan},
title = {{From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.16},
URN = {urn:nbn:de:0030-drops-194357},
doi = {10.4230/LIPIcs.IPEC.2023.16},
annote = {Keywords: Independent Set, Powers of Hypercubes, Diversity, Parameterized Complexity, Incomplete Data}
}
Document
Approximate Monotone Local Search for Weighted Problems
Abstract
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting.
More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover, d-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most α ⋅ W (and of arbitrary cardinality) in time c^k ⋅ n^{𝒪(1)} where W is the minimum weight of a solution of cardinality at most k. In the unweighted setting, Esmer et al. determine the smallest value d for which a β-approximation algorithm running in time dⁿ ⋅ n^{𝒪(1)} can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed ε > 0 we obtain a β-approximation algorithm running in time 𝒪((d+ε)ⁿ), for the same d as in the unweighted setting.
Similarly, we also extend a β-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time β-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted d-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.
Cite as
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Approximate Monotone Local Search for Weighted Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{esmer_et_al:LIPIcs.IPEC.2023.17,
author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
title = {{Approximate Monotone Local Search for Weighted Problems}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {17:1--17:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.17},
URN = {urn:nbn:de:0030-drops-194360},
doi = {10.4230/LIPIcs.IPEC.2023.17},
annote = {Keywords: parameterized approximations, exponential approximations, monotone local search}
}
Document
Consistency Checking Problems: A Gateway to Parameterized Sample Complexity
Abstract
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is that for a very wide range of learning problems, there is a direct and provable correspondence between fixed-parameter PAC-learnability (in the sample complexity setting) and the fixed-parameter tractability of a corresponding "consistency checking" search problem (in the setting of computational complexity). The latter can be seen as generalizations of classical search problems where instead of receiving a single instance, one receives multiple yes- and no-examples and is tasked with finding a solution which is consistent with the provided examples.
Apart from a few initial results, consistency checking problems are almost entirely unexplored from a parameterized complexity perspective. In this article, we provide an overview of these problems and their connection to parameterized sample complexity, with the primary aim of facilitating further research in this direction. Afterwards, we establish the fixed-parameter (in)-tractability for some of the arguably most natural consistency checking problems on graphs, and show that their complexity-theoretic behavior is surprisingly very different from that of classical decision problems. Our new results cover consistency checking variants of problems as diverse as (k-)Path, Matching, 2-Coloring, Independent Set and Dominating Set, among others.
Cite as
Robert Ganian, Liana Khazaliya, and Kirill Simonov. Consistency Checking Problems: A Gateway to Parameterized Sample Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{ganian_et_al:LIPIcs.IPEC.2023.18,
author = {Ganian, Robert and Khazaliya, Liana and Simonov, Kirill},
title = {{Consistency Checking Problems: A Gateway to Parameterized Sample Complexity}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {18:1--18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.18},
URN = {urn:nbn:de:0030-drops-194374},
doi = {10.4230/LIPIcs.IPEC.2023.18},
annote = {Keywords: consistency checking, sample complexity, fixed-parameter tractability}
}
Document
Finding Degree-Constrained Acyclic Orientations
Abstract
We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex v is in a prescribed list λ(v). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem is closely related to the classical General Factor problem, which is known to be NP-hard in general, but polynomial-time solvable if no list λ(v) contains large "gaps" [Cornuéjols, J. Comb. Theory B, 1988]. In contrast, we show that deciding if an acyclic orientation exists is NP-hard even in the absence of such "gaps".
On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of G (a smaller parameter than the frequently employed "level"), by the number of vertices v for which |λ(v)| ≥ 2, by the number of vertices v for which the highest value in λ(v) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].
Cite as
Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller. Finding Degree-Constrained Acyclic Orientations. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{garvardt_et_al:LIPIcs.IPEC.2023.19,
author = {Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias},
title = {{Finding Degree-Constrained Acyclic Orientations}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.19},
URN = {urn:nbn:de:0030-drops-194383},
doi = {10.4230/LIPIcs.IPEC.2023.19},
annote = {Keywords: Graph Orientation, Phylogenetic Networks, General Factor, NP-hardness, Parameterized Algorithms, Treewidth}
}
Document
Graph Clustering Problems Under the Lens of Parameterized Local Search
Abstract
Cluster Editing is the problem of finding the minimum number of edge-modifications that transform a given graph G into a cluster graph G', that is, each connected component of G' is a clique. Similarly, in the Cluster Deletion problem, we further restrict the sought cluster graph G' to contain only edges that are also present in G. In this work, we consider the parameterized complexity of a local search variant for both problems: LS Cluster Deletion and LS Cluster Editing. Herein, the input also comprises an integer k and a partition 𝒞 of the vertex set of G that describes an initial cluster graph G^*, and we are to decide whether the "k-move-neighborhood" of G^* contains a cluster graph G' that is "better" (uses less modifications) than G^*. Roughly speaking, two cluster graphs G₁ and G₂ are k-move-neighbors if G₁ can be obtained from G₂ by moving at most k vertices to different connected components.
We consider parameterizations by k + 𝓁 for some natural parameters 𝓁, such as the number of clusters in 𝒞, the size of a largest cluster in 𝒞, or the cluster-vertex-deletion number (cvd) of G. Our main lower-bound results are that LS Cluster Editing is W[1]-hard when parameterized by k even if 𝒞 has size two and that both LS Cluster Deletion and LS Cluster Editing are W[1]-hard when parameterized by k + 𝓁, where 𝓁 is the size of the largest cluster of 𝒞. On the positive side, we show that both problems admit an algorithm that runs in k^{𝒪(k)}⋅ cvd^{3k} ⋅ n^{𝒪(1)} time and either finds a better cluster graph or correctly outputs that there is no better cluster graph in the k-move-neighborhood of the initial cluster graph.
As an intermediate result, we also obtain an algorithm that solves Cluster Deletion in cvd^{cvd} ⋅ n^{𝒪(1)} time.
Cite as
Jaroslav Garvardt, Nils Morawietz, André Nichterlein, and Mathias Weller. Graph Clustering Problems Under the Lens of Parameterized Local Search. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{garvardt_et_al:LIPIcs.IPEC.2023.20,
author = {Garvardt, Jaroslav and Morawietz, Nils and Nichterlein, Andr\'{e} and Weller, Mathias},
title = {{Graph Clustering Problems Under the Lens of Parameterized Local Search}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.20},
URN = {urn:nbn:de:0030-drops-194391},
doi = {10.4230/LIPIcs.IPEC.2023.20},
annote = {Keywords: parameterized local search, permissive local search, FPT, W\lbrack1\rbrack-hardness}
}
Document
Bandwidth Parameterized by Cluster Vertex Deletion Number
Abstract
Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.
Cite as
Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, and Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gima_et_al:LIPIcs.IPEC.2023.21,
author = {Gima, Tatsuya and Kim, Eun Jung and K\"{o}hler, Noleen and Melissinos, Nikolaos and Vasilakis, Manolis},
title = {{Bandwidth Parameterized by Cluster Vertex Deletion Number}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.21},
URN = {urn:nbn:de:0030-drops-194401},
doi = {10.4230/LIPIcs.IPEC.2023.21},
annote = {Keywords: Bandwidth, Clique number, Cluster vertex deletion number, Parameterized complexity}
}
Document
Collective Graph Exploration Parameterized by Vertex Cover
Abstract
We initiate the study of the parameterized complexity of the Collective Graph Exploration (CGE) problem. In CGE, the input consists of an undirected connected graph G and a collection of k robots, initially placed at the same vertex r of G, and each one of them has an energy budget of B. The objective is to decide whether G can be explored by the k robots in B time steps, i.e., there exist k closed walks in G, one corresponding to each robot, such that every edge is covered by at least one walk, every walk starts and ends at the vertex r, and the maximum length of any walk is at most B. Unfortunately, this problem is NP-hard even on trees [Fraigniaud et al., 2006]. Further, we prove that the problem remains W[1]-hard parameterized by k even for trees of treedepth 3. Due to the para-NP-hardness of the problem parameterized by treedepth, and motivated by real-world scenarios, we study the parameterized complexity of the problem parameterized by the vertex cover number (vc) of the graph, and prove that the problem is fixed-parameter tractable (FPT) parameterized by vc. Additionally, we study the optimization version of CGE, where we want to optimize B, and design an approximation algorithm with an additive approximation factor of O(vc).
Cite as
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Collective Graph Exploration Parameterized by Vertex Cover. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.22,
author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav},
title = {{Collective Graph Exploration Parameterized by Vertex Cover}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {22:1--22:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.22},
URN = {urn:nbn:de:0030-drops-194413},
doi = {10.4230/LIPIcs.IPEC.2023.22},
annote = {Keywords: Collective Graph Exploration, Parameterized Complexity, Approximation Algorithm, Vertex Cover, Treedepth}
}
Document
Drawn Tree Decomposition: New Approach for Graph Drawing Problems
Abstract
Over the past decade, we witness an increasing amount of interest in the design of exact exponential-time and parameterized algorithms for problems in Graph Drawing. Unfortunately, we still lack knowledge of general methods to develop such algorithms. An even more serious issue is that, here, "standard" parameters very often yield intractability. In particular, for the most common structural parameter, namely, treewidth, we frequently observe NP-hardness already when the input graphs are restricted to have constant (often, being just 1 or 2) treewidth.
Our work deals with both drawbacks simultaneously. We introduce a novel form of tree decomposition that, roughly speaking, does not decompose (only) a graph, but an entire drawing. As such, its bags and separators are of geometric (rather than only combinatorial) nature. While the corresponding parameter - like treewidth - can be arbitrarily smaller than the height (and width) of the drawing, we show that - unlike treewidth - it gives rise to efficient algorithms. Specifically, we get slice-wise polynomial (XP) time algorithms parameterized by our parameter. We present a general scheme for the design of such algorithms, and apply it to several central problems in Graph Drawing, including the recognition of grid graphs, minimization of crossings and bends, and compaction. Other than for the class of problems we discussed in the paper, we believe that our decomposition and scheme are of independent interest and can be further extended or generalized to suit even a wider class of problems. Additionally, we discuss classes of drawings where our parameter is bounded by 𝒪(√n) (where n is the number of vertices of the graph), yielding subexponential-time algorithms. Lastly, we prove which relations exist between drawn treewidth and other width measures, including treewidth, pathwidth, (dual) carving-width and embedded-width.
Cite as
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi. Drawn Tree Decomposition: New Approach for Graph Drawing Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{gupta_et_al:LIPIcs.IPEC.2023.23,
author = {Gupta, Siddharth and Sa'ar, Guy and Zehavi, Meirav},
title = {{Drawn Tree Decomposition: New Approach for Graph Drawing Problems}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {23:1--23:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.23},
URN = {urn:nbn:de:0030-drops-194424},
doi = {10.4230/LIPIcs.IPEC.2023.23},
annote = {Keywords: Graph Drawing, Parameterized Complexity, Tree decomposition}
}
Document
Single Machine Scheduling with Few Deadlines
Abstract
We study single-machine scheduling problems with few deadlines. We focus on two classical objectives, namely minimizing the weighted number of tardy jobs and the total weighted completion time. For both problems, we give a pseudopolynomial-time algorithm for a constant number of different deadlines. This algorithm is complemented with an ETH-based, almost tight lower bound. Furthermore, we study the case where the number of jobs with a nontrivial deadline is taken as parameter. For this case, the complexity of our two problems differ: Minimizing the total number of tardy jobs becomes fixed-parameter tractable, while minimizing the total weighted completion time is W[1]-hard.
Cite as
Klaus Heeger, Danny Hermelin, and Dvir Shabtay. Single Machine Scheduling with Few Deadlines. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{heeger_et_al:LIPIcs.IPEC.2023.24,
author = {Heeger, Klaus and Hermelin, Danny and Shabtay, Dvir},
title = {{Single Machine Scheduling with Few Deadlines}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.24},
URN = {urn:nbn:de:0030-drops-194434},
doi = {10.4230/LIPIcs.IPEC.2023.24},
annote = {Keywords: Single-machine scheduling, weighted completion time, tardy jobs, pseudopolynomial algorithms, parameterized complexity}
}
Document
Twin-Width of Graphs with Tree-Structured Decompositions
Abstract
The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 [Édouard Bonnet et al., 2022; Édouard Bonnet et al., 2020], a mass of new results has appeared relating twin width to group theory, model theory, combinatorial optimization, and structural graph theory.
We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph is at most twice its strong tree-width, contrasting nicely with the result of [Édouard Bonnet and Hugues Déprés, 2023; Édouard Bonnet and Hugues Déprés, 2022], which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain optimal linear bounds on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph.
Cite as
Irene Heinrich and Simon Raßmann. Twin-Width of Graphs with Tree-Structured Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{heinrich_et_al:LIPIcs.IPEC.2023.25,
author = {Heinrich, Irene and Ra{\ss}mann, Simon},
title = {{Twin-Width of Graphs with Tree-Structured Decompositions}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.25},
URN = {urn:nbn:de:0030-drops-194449},
doi = {10.4230/LIPIcs.IPEC.2023.25},
annote = {Keywords: twin-width, quasi-4 connected components, strong tree-width}
}
Document
Dynamic Programming on Bipartite Tree Decompositions
Abstract
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.
Cite as
Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic Programming on Bipartite Tree Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jaffke_et_al:LIPIcs.IPEC.2023.26,
author = {Jaffke, Lars and Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
title = {{Dynamic Programming on Bipartite Tree Decompositions}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {26:1--26:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.26},
URN = {urn:nbn:de:0030-drops-194455},
doi = {10.4230/LIPIcs.IPEC.2023.26},
annote = {Keywords: tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal}
}
Document
Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions
Abstract
A kernelization for a parameterized decision problem 𝒬 is a polynomial-time preprocessing algorithm that reduces any parameterized instance (x,k) into an instance (x',k') whose size is bounded by a function of k alone and which has the same yes/no answer for 𝒬. Such preprocessing algorithms cannot exist in the context of counting problems, when the answer to be preserved is the number of solutions, since this number can be arbitrarily large compared to k. However, we show that for counting minimum feedback vertex sets of size at most k, and for counting minimum dominating sets of size at most k in a planar graph, there is a polynomial-time algorithm that either outputs the answer or reduces to an instance (G',k') of size polynomial in k with the same number of minimum solutions. This shows that a meaningful theory of kernelization for counting problems is possible and opens the door for future developments. Our algorithms exploit that if the number of solutions exceeds 2^{poly(k)}, the size of the input is exponential in terms of k so that the running time of a parameterized counting algorithm can be bounded by poly(n). Otherwise, we can use gadgets that slightly increase k to represent choices among 2^{𝒪(k)} options by only poly(k) vertices.
Cite as
Bart M. P. Jansen and Bart van der Steenhoven. Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.27,
author = {Jansen, Bart M. P. and van der Steenhoven, Bart},
title = {{Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {27:1--27:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.27},
URN = {urn:nbn:de:0030-drops-194466},
doi = {10.4230/LIPIcs.IPEC.2023.27},
annote = {Keywords: kernelization, counting problems, feedback vertex set, dominating set, protrusion decomposition}
}
Document
On the Parameterized Complexity of Multiway Near-Separator
Abstract
We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph G, integer k, and terminal set T ⊆ V(G), it asks whether there is a vertex set S ⊆ V(G) ⧵ T of size at most k such that in graph G-S, no pair of distinct terminals can be connected by two pairwise internally vertex-disjoint paths. Hence each terminal pair can be separated in G-S by removing at most one vertex. The problem is therefore a generalization of (Node) Multiway Cut, which asks for a vertex set for which each terminal is in a different component of G-S. We develop a fixed-parameter tractable algorithm for Multiway Near-Separator running in time 2^{𝒪(k log k)} ⋅ n^{𝒪(1)}. Our algorithm is based on a new pushing lemma for solutions with respect to important separators, along with two problem-specific ingredients. The first is a polynomial-time subroutine to reduce the number of terminals in the instance to a polynomial in the solution size k plus the size of a given suboptimal solution. The second is a polynomial-time algorithm that, given a graph G and terminal set T ⊆ V(G) along with a single vertex x ∈ V(G) that forms a multiway near-separator, computes a 14-approximation for the problem of finding a multiway near-separator not containing x.
Cite as
Bart M. P. Jansen and Shivesh K. Roy. On the Parameterized Complexity of Multiway Near-Separator. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.28,
author = {Jansen, Bart M. P. and Roy, Shivesh K.},
title = {{On the Parameterized Complexity of Multiway Near-Separator}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {28:1--28:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.28},
URN = {urn:nbn:de:0030-drops-194470},
doi = {10.4230/LIPIcs.IPEC.2023.28},
annote = {Keywords: fixed-parameter tractability, multiway cut, near-separator}
}
Document
Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs
Abstract
We study the kernelization complexity of the Weighted H-Packing problem on sparse graphs. For a fixed connected graph H, in the Weighted H-Packing problem the input is a graph G, a vertex-weight function w : V(G) → ℕ, and positive integers k, t. The question is whether there exist k vertex-disjoint subgraphs H₁, …, H_k of G such that H_i is isomorphic to H for each i ∈ [k] and the total weight of these k ⋅ |V(H)| vertices is at least t. It is known that the (unweighted) H-Packing problem admits a kernel with 𝒪(k^{|V(H)|-1}) vertices on general graphs, and a linear kernel on planar graphs and graphs of bounded genus. In this work, we focus on case that H is a clique on h ≥ 3 vertices (which captures Triangle Packing) and present a linear-vertex kernel for Weighted K_h-Packing on graphs of bounded expansion, along with a kernel with 𝒪(k^{1+ε}) vertices on nowhere-dense graphs for all ε > 0. To obtain these results, we combine two powerful ingredients in a novel way: the Erdős-Rado Sunflower lemma and the theory of sparsity.
Cite as
Bart M. P. Jansen and Shivesh K. Roy. Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.29,
author = {Jansen, Bart M. P. and Roy, Shivesh K.},
title = {{Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.29},
URN = {urn:nbn:de:0030-drops-194488},
doi = {10.4230/LIPIcs.IPEC.2023.29},
annote = {Keywords: kernelization, weighted problems, graph packing, sunflower lemma, bounded expansion, nowhere dense}
}
Document
How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks
Abstract
Phylogenetic Diversity (PD) is a measure of the overall biodiversity of a set of present-day species (taxa) within a phylogenetic tree. We consider an extension of PD to phylogenetic networks. Given a phylogenetic network with weighted edges and a subset S of leaves, the all-paths phylogenetic diversity of S is the summed weight of all edges on a path from the root to some leaf in S. The problem of finding a bounded-size set S that maximizes this measure is polynomial-time solvable on trees, but NP-hard on networks. We study the latter from a parameterized perspective.
While this problem is W[2]-hard with respect to the size of S (and W[1]-hard with respect to the size of the complement of S), we show that it is FPT with respect to several other parameters, including the phylogenetic diversity of S, the acceptable loss of phylogenetic diversity, the number of reticulations in the network, and the treewidth of the underlying graph.
Cite as
Mark Jones and Jannik Schestag. How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jones_et_al:LIPIcs.IPEC.2023.30,
author = {Jones, Mark and Schestag, Jannik},
title = {{How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {30:1--30:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.30},
URN = {urn:nbn:de:0030-drops-194496},
doi = {10.4230/LIPIcs.IPEC.2023.30},
annote = {Keywords: Phylogenetic Networks, Phylogenetic Diversity, Parameterized Complexity, W-hierarchy, FPT algorithms}
}
Document
Sidestepping Barriers for Dominating Set in Parameterized Complexity
Abstract
We study the classic Dominating Set problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterization. Our results span several parameterization regimes, including: (i,ii,iii) time/ratio-tradeoff for the parameters treewidth, vertex modulator to constant treewidth and solution size; (iv,v) FPT-algorithms for the parameters vertex cover number and feedback edge set number; and (vi) compression for the parameter feedback edge set number.
Cite as
Ioannis Koutis, Michał Włodarczyk, and Meirav Zehavi. Sidestepping Barriers for Dominating Set in Parameterized Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{koutis_et_al:LIPIcs.IPEC.2023.31,
author = {Koutis, Ioannis and W{\l}odarczyk, Micha{\l} and Zehavi, Meirav},
title = {{Sidestepping Barriers for Dominating Set in Parameterized Complexity}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {31:1--31:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.31},
URN = {urn:nbn:de:0030-drops-194506},
doi = {10.4230/LIPIcs.IPEC.2023.31},
annote = {Keywords: Dominating Set, Parameterized Complexity, Approximation Algorithms}
}
Document
Approximate Turing Kernelization and Lower Bounds for Domination Problems
Abstract
An α-approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an (α c)-approximate solution for a parameterized optimization problem when given access to an oracle that can compute c-approximate solutions to instances with size bounded by a polynomial in the parameter. Hols et al. [ESA 2020] showed that a wide array of graph problems admit a (1+ε)-approximate polynomial Turing kernelization when parameterized by the treewidth of the graph and left open whether Dominating Set also admits such a kernelization.
We show that Dominating Set and several related problems parameterized by treewidth do not admit constant-factor approximate polynomial Turing kernelizations, even with respect to the much larger parameter vertex cover number, under certain reasonable complexity assumptions. On the positive side, we show that all of them do have a (1+ε)-approximate polynomial Turing kernelization for every ε > 0 for the joint parameterization by treewidth and maximum degree, a parameter which generalizes cutwidth, for example.
Cite as
Stefan Kratsch and Pascal Kunz. Approximate Turing Kernelization and Lower Bounds for Domination Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kratsch_et_al:LIPIcs.IPEC.2023.32,
author = {Kratsch, Stefan and Kunz, Pascal},
title = {{Approximate Turing Kernelization and Lower Bounds for Domination Problems}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {32:1--32:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.32},
URN = {urn:nbn:de:0030-drops-194516},
doi = {10.4230/LIPIcs.IPEC.2023.32},
annote = {Keywords: Approximate Turing kernelization, approximation lower bounds, exponential-time hypothesis, dominating set, capacitated dominating, connected dominating set, independent dominating set, treewidth, vertex cover number}
}
Document
A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items
Abstract
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also 𝖶[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question.
In this work, we make progress towards this goal by showing a PAS under the following assumptions:
- both the box and all the input rectangles have integral, polynomially bounded sidelengths;
- every input rectangle is wide - its width is greater than its height; and
- the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.
Cite as
Mathieu Mari, Timothé Picavet, and Michał Pilipczuk. A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{mari_et_al:LIPIcs.IPEC.2023.33,
author = {Mari, Mathieu and Picavet, Timoth\'{e} and Pilipczuk, Micha{\l}},
title = {{A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {33:1--33:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.33},
URN = {urn:nbn:de:0030-drops-194529},
doi = {10.4230/LIPIcs.IPEC.2023.33},
annote = {Keywords: Parameterized complexity, Approximation scheme, Geometric knapsack, Color coding, Dynamic programming, Computational geometry}
}
Document
A Contraction-Recursive Algorithm for Treewidth
Abstract
Let tw(G) denote the treewidth of graph G. Given a graph G and a positive integer k such that tw(G) ≤ k + 1, we are to decide if tw(G) ≤ k. We give a certifying algorithm RTW ("R" for recursive) for this task: it returns one or more tree-decompositions of G of width ≤ k if the answer is YES and a minimal contraction H of G such that tw(H) > k otherwise. Starting from a greedy upper bound on tw(G) and repeatedly improving the upper bound by this algorithm, we obtain tw(G) with certificates.
RTW uses a heuristic variant of Tamaki’s PID algorithm for treewidth (ESA2017), which we call HPID. Informally speaking, PID builds potential subtrees of tree-decompositions of width ≤ k in a bottom up manner, until such a tree-decomposition is constructed or the set of potential subtrees is exhausted without success. HPID uses the same method of generating a new subtree from existing ones but with a different generation order which is not intended for exhaustion but for quick generation of a full tree-decomposition when possible. RTW, given G and k, interleaves the execution of HPID with recursive calls on G /e for edges e of G, where G / e denotes the graph obtained from G by contracting edge e. If we find that tw(G / e) > k, then we have tw(G) > k with the same certificate. If we find that tw(G / e) ≤ k, we "uncontract" the bags of the certifying tree-decompositions of G / e into bags of G and feed them to HPID to help progress. If the question is not resolved after the recursive calls are made for all edges, we finish HPID in an exhaustive mode. If it turns out that tw(G) > k, then G is a certificate for tw(G') > k for every G' of which G is a contraction, because we have found tw(G / e) ≤ k for every edge e of G. This final round of HPID guarantees the correctness of the algorithm, while its practical efficiency derives from our methods of "uncontracting" bags of tree-decompositions of G / e to useful bags of G, as well as of exploiting those bags in HPID.
Experiments show that our algorithm drastically extends the scope of practically solvable instances. In particular, when applied to the 100 instances in the PACE 2017 bonus set, the number of instances solved by our implementation on a typical laptop, with the timeout of 100, 1000, and 10000 seconds per instance, are 72, 92, and 98 respectively, while these numbers are 11, 38, and 68 for Tamaki’s PID solver and 65, 82, and 85 for his new solver (SEA 2022).
Cite as
Hisao Tamaki. A Contraction-Recursive Algorithm for Treewidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{tamaki:LIPIcs.IPEC.2023.34,
author = {Tamaki, Hisao},
title = {{A Contraction-Recursive Algorithm for Treewidth}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {34:1--34:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.34},
URN = {urn:nbn:de:0030-drops-194536},
doi = {10.4230/LIPIcs.IPEC.2023.34},
annote = {Keywords: graph algorithm, treewidth, exact computation, BT dynamic programming, contraction, certifying algorithms}
}
Document
PACE Solver Description
PACE Solver Description: The PACE 2023 Parameterized Algorithms and Computational Experiments Challenge: Twinwidth
Abstract
This article is a report by the challenge organizers on the 8th Parameterized Algorithms and Computational Experiments Challenge (PACE 2023). As was common in previous iterations of the competition, this year’s iteration implemented an exact and heuristic track for a parameterized problem that has gained attention in the theory community. This year, the problem was to compute the twinwidth of a graph, a recently introduced width parameter that measures the similarity of a graph to a cograph. In the exact track, the competition participants were asked to develop an exact algorithm that can solve as many instances as possible from a benchmark set of 100 instances - with a time limit of 30 minutes per instance. The same task must be accomplished within 5 minutes in the heuristic track. However, the result in this track is not required to be optimal.
As in previous iterations, the organizers handed out awards to the best solutions in both tracks and to the best student submissions. New this year is a dedicated theory award that appreciates new theoretical insights found by the participants during the development of their tools.
Cite as
Max Bannach and Sebastian Berndt. PACE Solver Description: The PACE 2023 Parameterized Algorithms and Computational Experiments Challenge: Twinwidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bannach_et_al:LIPIcs.IPEC.2023.35,
author = {Bannach, Max and Berndt, Sebastian},
title = {{PACE Solver Description: The PACE 2023 Parameterized Algorithms and Computational Experiments Challenge: Twinwidth}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.35},
URN = {urn:nbn:de:0030-drops-194548},
doi = {10.4230/LIPIcs.IPEC.2023.35},
annote = {Keywords: Twinwidth, Algorithm Engineering, FPT, Kernelization}
}
Document
PACE Solver Description
PACE Solver Description: Hydra Prime
Abstract
This note describes our submission to the 2023 PACE Challenge on the computation of twin-width. Our solver Hydra Prime combines modular decomposition with a collection of upper- and lower-bound algorithms, which are alternatingly applied on the prime graphs resulting from the modular decomposition. We introduce two novel approaches which contributed to the solver’s winning performance in the Exact Track: timeline encoding and hydra decomposition. Timeline encoding is a new data structure for computing the width of a given contraction sequence, enabling faster local search; the hydra decomposition is an iterative refinement strategy featuring a small vertex separator.
Cite as
Yosuke Mizutani, David Dursteler, and Blair D. Sullivan. PACE Solver Description: Hydra Prime. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 36:1-36:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{mizutani_et_al:LIPIcs.IPEC.2023.36,
author = {Mizutani, Yosuke and Dursteler, David and Sullivan, Blair D.},
title = {{PACE Solver Description: Hydra Prime}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {36:1--36:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.36},
URN = {urn:nbn:de:0030-drops-194552},
doi = {10.4230/LIPIcs.IPEC.2023.36},
annote = {Keywords: Twin-width, PACE 2023}
}
Document
PACE Solver Description
PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)
Abstract
Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track.
Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch.
Cite as
Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck. PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM). In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{leonhardt_et_al:LIPIcs.IPEC.2023.37,
author = {Leonhardt, Alexander and Dell, Holger and Haak, Anselm and Kammer, Frank and Meintrup, Johannes and Meyer, Ulrich and Penschuck, Manuel},
title = {{PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {37:1--37:7},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37},
URN = {urn:nbn:de:0030-drops-194563},
doi = {10.4230/LIPIcs.IPEC.2023.37},
annote = {Keywords: PACE 2023 Challenge, Heuristic, Exact, Twin-Width}
}
Document
PACE Solver Description
PACE Solver Description: Touiouidth
Abstract
We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.
Cite as
Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: Touiouidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{berthe_et_al:LIPIcs.IPEC.2023.38,
author = {Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Dobler, Alexander and Morelle, Laure and Reinald, Amadeus and Rocton, Mathis},
title = {{PACE Solver Description: Touiouidth}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {38:1--38:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.38},
URN = {urn:nbn:de:0030-drops-194576},
doi = {10.4230/LIPIcs.IPEC.2023.38},
annote = {Keywords: Twinwidth, Pace Challenge}
}
Document
PACE Solver Description
PACE Solver Description: Zygosity
Abstract
The graph parameter twin-width was recently introduced by Bonnet et al. Twin-width is a parameter that measures a graph’s similarity to a cograph, which is a graph that can be reduced to a single vertex by repeatedly contracting twins. This brief description introduces Zygosity, a heuristic for computing a low-width contraction sequence that achieved second place in the 2023 edition of Parameterized Algorithms and Computational Experiments Challenge (PACE). Zygosity starts by repeatedly contracting twins. Then, any attached trees are contracted down to a single pendant vertex. The remaining graph is then contracted using a randomized greedy algorithm.
Cite as
Emmanuel Arrighi, Pål Grønås Drange, Kenneth Langedal, Farhad Vadiee, Martin Vatshelle, and Petra Wolf. PACE Solver Description: Zygosity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.39,
author = {Arrighi, Emmanuel and Drange, P\r{a}l Gr{\o}n\r{a}s and Langedal, Kenneth and Vadiee, Farhad and Vatshelle, Martin and Wolf, Petra},
title = {{PACE Solver Description: Zygosity}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {39:1--39:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.39},
URN = {urn:nbn:de:0030-drops-194583},
doi = {10.4230/LIPIcs.IPEC.2023.39},
annote = {Keywords: Twin-width, randomized greedy algorithm}
}
Document
PACE Solver Description
PACE Solver Description: RedAlert - Heuristic Track
Abstract
We present RedAlert, a heuristic solver for twin-width, submitted to the Heuristic Track of the 2023 edition of the Parameterized Algorithms and Computational Experiments (PACE) challenge.
Cite as
Édouard Bonnet and Julien Duron. PACE Solver Description: RedAlert - Heuristic Track. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 40:1-40:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2023.40,
author = {Bonnet, \'{E}douard and Duron, Julien},
title = {{PACE Solver Description: RedAlert - Heuristic Track}},
booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {40:1--40:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-305-8},
ISSN = {1868-8969},
year = {2023},
volume = {285},
editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.40},
URN = {urn:nbn:de:0030-drops-194591},
doi = {10.4230/LIPIcs.IPEC.2023.40},
annote = {Keywords: twin-width, contraction sequences, heuristic, pair sampling, pair filtering}
}