Search Results

Documents authored by Gaspers, Serge

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.69
Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems

Authors: Serge Gaspers and Jerry Zirui Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.
Cite as

Serge Gaspers and Jerry Zirui Li. Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ICALP.2024.69,
  author =	{Gaspers, Serge and Li, Jerry Zirui},
  title =	{{Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{69:1--69:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.69},
  URN =		{urn:nbn:de:0030-drops-202124},
  doi =		{10.4230/LIPIcs.ICALP.2024.69},
  annote =	{Keywords: Graph algorithms, quantum algorithms, graph coloring, domatic number, set cover, set partition, set packing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.59
Minimizing and Computing the Inverse Geodesic Length on Trees

Authors: Serge Gaspers and Joshua Lau

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
For any fixed measure H that maps graphs to real numbers, the MinH problem is defined as follows: given a graph G, an integer k, and a target tau, is there a set S of k vertices that can be deleted, so that H(G - S) is at most tau? In this paper, we consider the MinH problem on trees. We call H balanced on trees if, whenever G is a tree, there is an optimal choice of S such that the components of G - S have sizes bounded by a polynomial in n / k. We show that MinH on trees is Fixed-Parameter Tractable (FPT) for parameter n / k, and furthermore, can be solved in subexponential time, and polynomial space, whenever H is additive, balanced on trees, and computable in polynomial time. A particular measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the efficiency and connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: IGL(G) = sum_{{u,v} subseteq V} 1/d_G(u,v). While MinIGL is W[1]-hard for parameter treewidth, and cannot be solved in 2^{o(k + n + m)} time, even on bipartite graphs with n vertices and m edges, the complexity status of the problem remains open in the case where G is a tree. We show that IGL is balanced on trees, to give a 2^O((n log n)^(5/6)) time, polynomial space algorithm. The distance distribution of G is the sequence {a_i} describing the number of vertex pairs distance i apart in G: a_i = |{{u, v}: d_G(u, v) = i}|. Given only the distance distribution, one can easily determine graph parameters such as diameter, Wiener index, and particularly, the IGL. We show that the distance distribution of a tree can be computed in O(n log^2 n) time by reduction to polynomial multiplication. We also extend the result to graphs with small treewidth by showing that the first p values of the distance distribution can be computed in 2^(O(tw(G))) n^(1 + epsilon) sqrt(p) time, and the entire distance distribution can be computed in 2^(O(tw(G))) n^{1 + epsilon} time, when the diameter of G is O(n^epsilon') for every epsilon' > 0.
Cite as

Serge Gaspers and Joshua Lau. Minimizing and Computing the Inverse Geodesic Length on Trees. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2019.59,
  author =	{Gaspers, Serge and Lau, Joshua},
  title =	{{Minimizing and Computing the Inverse Geodesic Length on Trees}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.59},
  URN =		{urn:nbn:de:0030-drops-115555},
  doi =		{10.4230/LIPIcs.ISAAC.2019.59},
  annote =	{Keywords: Trees, Treewidth, Fixed-Parameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.74
Enumeration of Preferred Extensions in Almost Oriented Digraphs

Authors: Serge Gaspers and Ray Li

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on n vertices, all preferred extensions can be enumerated in O^*(3^{n/3}) time and there are directed graphs with Omega(3^{n/3}) preferred extensions. We give faster enumeration algorithms for directed graphs with at most 0.8004 * n vertices occurring in 2-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time O(1.2321^n), and we show that there are oriented graphs with Omega(3^{n/6}) > Omega(1.2009^n) preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in 2-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017).
Cite as

Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.MFCS.2019.74,
  author =	{Gaspers, Serge and Li, Ray},
  title =	{{Enumeration of Preferred Extensions in Almost Oriented Digraphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{74:1--74:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.74},
  URN =		{urn:nbn:de:0030-drops-110188},
  doi =		{10.4230/LIPIcs.MFCS.2019.74},
  annote =	{Keywords: abstract argumentation, exact algorithms, exponential time algorithms, parameterized algorithms, enumeration algorithms, semikernels in digraphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.35
Colouring Square-Free Graphs without Long Induced Paths

Authors: Serge Gaspers, Shenwei Huang, and Daniel Paulusma

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs.
Cite as

Serge Gaspers, Shenwei Huang, and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.STACS.2018.35,
  author =	{Gaspers, Serge and Huang, Shenwei and Paulusma, Daniel},
  title =	{{Colouring Square-Free Graphs without Long Induced Paths}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.35},
  URN =		{urn:nbn:de:0030-drops-84922},
  doi =		{10.4230/LIPIcs.STACS.2018.35},
  annote =	{Keywords: graph colouring, hereditary graph class, clique-width, cycle, path}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.37
Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements

Authors: Serge Gaspers, Joachim Gudmundsson, Julián Mestre, and Stefan Rümmele

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Given a line segment I=[0,L], the so-called barrier, and a set of n sensors with varying ranges positioned on the line containing I, the barrier coverage problem is to move the sensors so that they cover I, while minimising the total movement. In the case when all the sensors have the same radius the problem can be solved in O(n log n) time (Andrews and Wang, Algorithmica 2017). If the sensors have different radii the problem is known to be NP-hard to approximate within a constant factor (Czyzowicz et al., ADHOC-NOW 2009). We strengthen this result and prove that no polynomial time \rho^{1-\epsilon}-approximation algorithm exists unless P=NP, where \rho is the ratio between the largest radius and the smallest radius. Even when we restrict the number of sensors that are allowed to move by a parameter k, the problem turns out to be W[1]-hard. On the positive side we show that a ((2+\epsilon)\rho+2/\epsilon)-approximation can be computed in O(n^3/\epsilon^2) time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.
Cite as

Serge Gaspers, Joachim Gudmundsson, Julián Mestre, and Stefan Rümmele. Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2017.37,
  author =	{Gaspers, Serge and Gudmundsson, Joachim and Mestre, Juli\'{a}n and R\"{u}mmele, Stefan},
  title =	{{Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.37},
  URN =		{urn:nbn:de:0030-drops-82591},
  doi =		{10.4230/LIPIcs.ISAAC.2017.37},
  annote =	{Keywords: Barrier coverage, Sensor movement, Approximation, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.69
Exact Algorithms via Multivariate Subroutines

Authors: Serge Gaspers and Edward J. Lee

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We consider the family of Phi-Subset problems, where the input consists of an instance I of size N over a universe U_I of size n and the task is to check whether the universe contains a subset with property Phi (e.g., Phi could be the property of being a feedback vertex set for the input graph of size at most k). Our main tool is a simple randomized algorithm which solves Phi-Subset in time (1+b-(1/c))^n N^(O(1)), provided that there is an algorithm for the Phi-Extension problem with running time b^{n-|X|} c^k N^{O(1)}. Here, the input for Phi-Extension is an instance I of size N over a universe U_I of size n, a subset X \subseteq U_I, and an integer k, and the task is to check whether there is a set Y with X \subseteq Y \subseteq U_I and |Y \ X| <= k with property Phi. We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in n, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property Phi. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where b=1. As case studies, we use these results to design faster deterministic algorithms for: - checking whether a graph has a feedback vertex set of size at most k - enumerating all minimal feedback vertex sets - enumerating all minimal vertex covers of size at most k, and - enumerating all minimal 3-hitting sets. We obtain these results by deriving new b^{n-|X|} c^k N^{O(1)}-time algorithms for the corresponding Phi-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, 1+b-(1/c), is unconventional and requires non-convex optimization.
Cite as

Serge Gaspers and Edward J. Lee. Exact Algorithms via Multivariate Subroutines. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ICALP.2017.69,
  author =	{Gaspers, Serge and Lee, Edward J.},
  title =	{{Exact Algorithms via Multivariate Subroutines}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{69:1--69:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.69},
  URN =		{urn:nbn:de:0030-drops-74251},
  doi =		{10.4230/LIPIcs.ICALP.2017.69},
  annote =	{Keywords: enumeration algorithms, exponential time algorithms, feedback vertex set, hitting set}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.90
The Parameterized Complexity of Positional Games

Authors: Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves an open problem from Downey and Fellows’ influential list of open problems from 1999. Previously, the problem was thought of as a natural candidate for AW[*]-completeness. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge, and the second player wins otherwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge, and the second player wins otherwise. Short Maker-Maker, Short Maker-Breaker, and Short Enforcer-Avoider are respectively AW[*]-, W[1]-, and co-W[1]-complete parameterized by the number of moves. This suggests a rough parameterized complexity categorization into positional games that are complete for the first level of the W-hierarchy when the winning condition only depends on which vertices one player has been able to pick, but AW[*]-complete when it depends on which vertices both players have picked. However, some positional games with highly structured board and winning configurations are fixed-parameter tractable. We give another example of such a game, Short k-Connect, which is fixed-parameter tractable when parameterized by the number of moves.
Cite as

Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine. The Parameterized Complexity of Positional Games. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2017.90,
  author =	{Bonnet, \'{E}douard and Gaspers, Serge and Lambilliotte, Antonin and R\"{u}mmele, Stefan and Saffidine, Abdallah},
  title =	{{The Parameterized Complexity of Positional Games}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{90:1--90:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.90},
  URN =		{urn:nbn:de:0030-drops-74941},
  doi =		{10.4230/LIPIcs.ICALP.2017.90},
  annote =	{Keywords: Hex, Maker-Maker games, Maker-Breaker games, Enforcer-Avoider games, parameterized complexity theory}
}
Document
DOI: 10.4230/DFU.Vol7.15301.137
Backdoor Sets for CSP

Authors: Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
A backdoor set of a CSP instance is a set of variables whose instantiation moves the instance into a fixed class of tractable instances (an island of tractability). An interesting algorithmic task is to find a small backdoor set efficiently: once it is found we can solve the instance by solving a number of tractable instances. Parameterized complexity provides an adequate framework for studying and solving this algorithmic task, where the size of the backdoor set provides a natural parameter. In this survey we present some recent parameterized complexity results on CSP backdoor sets, focusing on backdoor sets into islands of tractability that are defined in terms of constraint languages.
Cite as

Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Backdoor Sets for CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 137-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{gaspers_et_al:DFU.Vol7.15301.137,
  author =	{Gaspers, Serge and Ordyniak, Sebastian and Szeider, Stefan},
  title =	{{Backdoor Sets for CSP}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{137--157},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.137},
  URN =		{urn:nbn:de:0030-drops-69626},
  doi =		{10.4230/DFU.Vol7.15301.137},
  annote =	{Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.13
Turbocharging Treewidth Heuristics

Authors: Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele

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

Abstract
A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution.
Cite as

Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging Treewidth Heuristics. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.IPEC.2016.13,
  author =	{Gaspers, Serge and Gudmundsson, Joachim and Jones, Mitchell and Mestre, Juli\'{a}n and R\"{u}mmele, Stefan},
  title =	{{Turbocharging Treewidth Heuristics}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.13},
  URN =		{urn:nbn:de:0030-drops-69322},
  doi =		{10.4230/LIPIcs.IPEC.2016.13},
  annote =	{Keywords: tree decomposition, heuristic, fixed-parameter tractability, local search}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.14
On Satisfiability Problems with a Linear Structure

Authors: Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle

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

Abstract
It was recently shown [Sæther, Telle, and Vatshelle, JAIR 54, 2015] that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite graph by omitting all edges within each partite set). Here we relax this condition in several directions: First, we show an FPT algorithm parameterized by k for k-interval bigraphs, bipartite graphs which can be converted to interval bipartite graphs by adding to each node of one side at most k edges; the same result holds for the counting and the weighted maximization version of satisfiability. Second, given two linear orders, one for the variables and one for the clauses, we show how to find, in polynomial time, the smallest k such that there is a k-interval bigraph compatible with these two orders. On the negative side we prove that, barring complexity collapses, no such extensions are possible for CSPs more general than satisfiability. We also show NP-hardness of recognizing 1-interval bigraphs.
Cite as

Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle. On Satisfiability Problems with a Linear Structure. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.IPEC.2016.14,
  author =	{Gaspers, Serge and Papadimitriou, Christos H. and S{\ae}ther, Sigve Hortemo and Telle, Jan Arne},
  title =	{{On Satisfiability Problems with a Linear Structure}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.14},
  URN =		{urn:nbn:de:0030-drops-69412},
  doi =		{10.4230/LIPIcs.IPEC.2016.14},
  annote =	{Keywords: Satisfiability, interval graphs, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.122
On the Complexity of Grammar-Based Compression over Fixed Alphabets

Authors: Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, and Markus L. Schmid

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the "hierarchical depth" on the complexity of the shortest-grammar problem).
Cite as

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, and Markus L. Schmid. On the Complexity of Grammar-Based Compression over Fixed Alphabets. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 122:1-122:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{casel_et_al:LIPIcs.ICALP.2016.122,
  author =	{Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.},
  title =	{{On the Complexity of Grammar-Based Compression over Fixed Alphabets}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{122:1--122:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.122},
  URN =		{urn:nbn:de:0030-drops-62570},
  doi =		{10.4230/LIPIcs.ICALP.2016.122},
  annote =	{Keywords: Grammar-Based Compression, Straight-Line Programs, NP-Completeness, Exact Exponential Time Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.67
Backdoors to q-Horn

Authors: Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
The class q-Horn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF formulas for which satisfiability can be decided in polynomial time. This class properly contains the fundamental classes of Horn and Krom formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we extend this class so that its favorable algorithmic properties can be made accessible to formulas that are outside but "close"' to this class. We show that deciding satisfiability is fixed-parameter tractable parameterized by the distance of the given formula from q-Horn. The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a q-Horn formula, i.e., the size of a smallest deletion backdoor set into the class q-Horn. This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, Krom, and renamable Horn.
Cite as

Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. Backdoors to q-Horn. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 67-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.STACS.2013.67,
  author =	{Gaspers, Serge and Ordyniak, Sebastian and Ramanujan, M. S. and Saurabh, Saket and Szeider, Stefan},
  title =	{{Backdoors to q-Horn}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{67--79},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.67},
  URN =		{urn:nbn:de:0030-drops-39236},
  doi =		{10.4230/LIPIcs.STACS.2013.67},
  annote =	{Keywords: Algorithms and data structures, Backdoor sets, Satisfiability, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2305
Kernels for Feedback Arc Set In Tournaments

Authors: Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
A tournament $T = (V,A)$ is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on $n$ vertices and an integer parameter $k$, the {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem. In thispaper we obtain a linear vertex kernel for \FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to \FAST{} obtains an equivalent instance $T'$ on $O(k)$ vertices. In fact, given any fixed $\epsilon > 0$, the kernelized instance has at most $(2 + \epsilon)k$ vertices.Our result improves the previous known bound of $O(k^2)$ on the kernel size for\FAST{}. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for \FAST.
Cite as

Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for Feedback Arc Set In Tournaments. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 37-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.FSTTCS.2009.2305,
  author =	{Bessy, St\'{e}phane and Fomin, Fedor V. and Gaspers, Serge and Paul, Christophe and Perez, Anthony and Saurabh, Saket and Thomass\'{e}, St\'{e}phan},
  title =	{{Kernels for Feedback Arc Set In Tournaments}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{37--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2305},
  URN =		{urn:nbn:de:0030-drops-23055},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2305},
  annote =	{Keywords: Parameterized complexity, kernels, tournaments}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact