Volume
LIPIcs, Volume 89
12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Event
IPEC 2017, September 6-8, 2017, Vienna, AustriaEditors
Publication Details
- published at: 2018-03-02
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-051-4
- DBLP: db/conf/iwpec/ipec2017
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 89, IPEC'17, Complete Volume
Abstract
LIPIcs, Volume 89, IPEC'17, Complete Volume
Cite as
12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@Proceedings{lokshtanov_et_al:LIPIcs.IPEC.2017,
title = {{LIPIcs, Volume 89, IPEC'17, Complete Volume}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017},
URN = {urn:nbn:de:0030-drops-86166},
doi = {10.4230/LIPIcs.IPEC.2017},
annote = {Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{lokshtanov_et_al:LIPIcs.IPEC.2017.0,
author = {Lokshtanov, Daniel and Nishimura, Naomi},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {0:i--0:xii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.0},
URN = {urn:nbn:de:0030-drops-85437},
doi = {10.4230/LIPIcs.IPEC.2017.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
On the Parameterized Complexity of Contraction to Generalization of Trees
Abstract
For a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S \subseteq E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al.[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied \cal F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let T_\ell be the family of graphs such that each graph in T_\ell can be made into a tree by deleting at most \ell edges. Thus, the problem we study is T_\ell-Contraction. We design an FPT algorithm for T_\ell-Contraction running in time O((\ncol)^{O(k + \ell)} * n^{O(1)}). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T_\ell-Contraction of size O([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha-1}\rceil + 1)}}).
Cite as
Akanksha Agrawal, Saket Saurabh, and Prafullkumar Tale. On the Parameterized Complexity of Contraction to Generalization of Trees. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{agrawal_et_al:LIPIcs.IPEC.2017.1,
author = {Agrawal, Akanksha and Saurabh, Saket and Tale, Prafullkumar},
title = {{On the Parameterized Complexity of Contraction to Generalization of Trees}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {1:1--1:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.1},
URN = {urn:nbn:de:0030-drops-85446},
doi = {10.4230/LIPIcs.IPEC.2017.1},
annote = {Keywords: Graph Contraction, Fixed Parameter Tractability, Graph Algorithms, Generalization of Trees}
}
Document
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
Abstract
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given graphs X_1=(V,E_1) and X_2=(V,E_2) and a subset R\subseteq V\times V of forbidden pairs whether there is an isomorphism \pi from X_1 to X_2 such that i^\pi\ne j for all (i,j)\in R. We prove that this problem and several of its generalizations are in fact in \FPT:
- The problem of deciding whether there is an isomorphism between two graphs that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result it follows that the problem to decide whether there is an isomorphism that moves exactly k vertices is in FPT. This solves a question left open in our article on exact weight automorphisms [STACS 2017].
- When the number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle.
- Checking if there is an isomorphism π between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that \pi can be expressed as a product of t transpositions.
- We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT.
In the non-parameterized setting, all these problems are NP-complete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].
Cite as
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{arvind_et_al:LIPIcs.IPEC.2017.2,
author = {Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo},
title = {{Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {2:1--2:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.2},
URN = {urn:nbn:de:0030-drops-85690},
doi = {10.4230/LIPIcs.IPEC.2017.2},
annote = {Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs}
}
Document
Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter
Abstract
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.
Cite as
Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos. Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{baste_et_al:LIPIcs.IPEC.2017.3,
author = {Baste, Julien and G\"{o}z\"{u}pek, Didem and Paul, Christophe and Sau, Ignasi and Shalom, Mordechai and Thilikos, Dimitrios M.},
title = {{Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {3:1--3:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.3},
URN = {urn:nbn:de:0030-drops-85545},
doi = {10.4230/LIPIcs.IPEC.2017.3},
annote = {Keywords: reload cost problems, minimum diameter spanning tree, parameterized complexity, FPT algorithm, treewidth, dynamic programming}
}
Document
Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth
Abstract
For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds:
- f_{K_4}(w) = 2^{Theta(wlog w)}.
- f_{C_i}(w) = 2^{Theta(w)} for every i<5, and f_{C_i}(w) = 2^{Theta(wlog w)} for every i>4.
- f_{P_i}(w) = 2^{Theta(w)} for every i<5, and f_{P_i}(w) = 2^{Theta(wlog w)} for every i>5.
The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.
Cite as
Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{baste_et_al:LIPIcs.IPEC.2017.4,
author = {Baste, Julien and Sau, Ignasi and Thilikos, Dimitrios M.},
title = {{Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {4:1--4:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.4},
URN = {urn:nbn:de:0030-drops-85556},
doi = {10.4230/LIPIcs.IPEC.2017.4},
annote = {Keywords: parameterized complexity, graph minors, treewidth, hitting minors, topological minors, dynamic programming, Exponential Time Hypothesis}
}
Document
Contraction-Bidimensionality of Geometric Intersection Graphs
Abstract
Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma_k. A graph class G has the SQGC property if every graph G in G has treewidth O(bcg(G)c) for some 1 <= c < 2. The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.
Cite as
Julien Baste and Dimitrios M. Thilikos. Contraction-Bidimensionality of Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{baste_et_al:LIPIcs.IPEC.2017.5,
author = {Baste, Julien and Thilikos, Dimitrios M.},
title = {{Contraction-Bidimensionality of Geometric Intersection Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {5:1--5:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.5},
URN = {urn:nbn:de:0030-drops-85487},
doi = {10.4230/LIPIcs.IPEC.2017.5},
annote = {Keywords: Grid exlusion theorem, Bidimensionality, Geometric intersection graphs, String Graphs}
}
Document
Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants
Abstract
We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q-1, our first data structure relies on (d+1)^{n+2} tabulated values of P to produce the value of P at any of the q^n points using O(nqd^2) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q-1, our second data structure assumes that P satisfies a degree-separability condition and relies on (d/s+1)^{n+s} tabulated values to produce the value of P at any point using O(nq^ssq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (2004), Saraf and Sudan (2008), and Dvir (2009) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves.
As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (2011) that captures numerous fundamental algebraic and combinatorial invariants such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m-by-m integer matrix with entries bounded in absolute value by a constant can be computed in time 2^{m-Omega(sqrt(m/log log m))}, improving an earlier algorithm of Bjorklund (2016) that runs in time 2^{m-Omega(sqrt(m/log m))}.
Cite as
Andreas Björklund, Petteri Kaski, and Ryan Williams. Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bjorklund_et_al:LIPIcs.IPEC.2017.6,
author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Williams, Ryan},
title = {{Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {6:1--6:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.6},
URN = {urn:nbn:de:0030-drops-85728},
doi = {10.4230/LIPIcs.IPEC.2017.6},
annote = {Keywords: Besicovitch set, fermionant, finite field, finite vector space, Hamiltonian cycle, homogeneous polynomial, Kakeya set, permanent, polynomial evaluatio}
}
Document
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms
Abstract
It has long been known that Feedback Vertex Set can be solved in time 2^O(w log w)n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class of graphs P, Bounded P-Block Vertex Deletion asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices
such that each block of G-S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:
- if P consists only of chordal graphs, then the problem can be solved in time 2^O(wd^2) n^{O}(1),
- if P contains a graph with an induced cycle of length ell>= 4, then the problem is not solvable in time 2^{o(w log w)} n^O(1)} even for fixed d=ell, unless the ETH fails.
We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size instead of having blocks of small size, and present analogous results.
Cite as
Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2017.7,
author = {Bonnet, \'{E}douard and Brettell, Nick and Kwon, O-joung and Marx, D\'{a}niel},
title = {{Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {7:1--7:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.7},
URN = {urn:nbn:de:0030-drops-85653},
doi = {10.4230/LIPIcs.IPEC.2017.7},
annote = {Keywords: fixed-parameter tractable algorithms, treewidth, feedback vertex set}
}
Document
On the Parameterized Complexity of Red-Blue Points Separation
Abstract
We study the following geometric separation problem: Given a set R of red points and a set B of blue points in the plane, find a minimum-size set of lines that separate R from B. We show that, in its full generality, parameterized by the number of lines k in the solution, the problem is unlikely to be solvable significantly faster than the brute-force n^{O(k)}-time algorithm, where n is the total number of points.
Indeed, we show that an algorithm running in time f(k)n^{o(k/log k)}, for any computable function f, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of k).
Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result.
Separating R from B with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time O^*(9^{|B|}) (assuming that B is the smallest set).
Cite as
Édouard Bonnet, Panos Giannopoulos, and Michael Lampis. On the Parameterized Complexity of Red-Blue Points Separation. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2017.8,
author = {Bonnet, \'{E}douard and Giannopoulos, Panos and Lampis, Michael},
title = {{On the Parameterized Complexity of Red-Blue Points Separation}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {8:1--8:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.8},
URN = {urn:nbn:de:0030-drops-85687},
doi = {10.4230/LIPIcs.IPEC.2017.8},
annote = {Keywords: red-blue points separation, geometric problem, W\lbrack1\rbrack-hardness, FPT algorithm, ETH-based lower bound}
}
Document
Relativization and Interactive Proof Systems in Parameterized Complexity Theory
Abstract
We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Grohe (2005) to characterize a number of parameterized complexity classes. Here we obtain a new and non-trivial characterization of the A-Hierarchy in terms of oracle machines, and parameterize a famous result of Baker, Gill, and Solovay (1975), by proving that, relative to specific oracles, FPT and A[1] can either coincide or differ (a similar statement holds for FPT and W[P]). Second, we initiate the study of interactive proof systems in the parameterized setting, and show that every problem in the class AW[SAT] has a proof system with "short" interactions, in the sense that the number of rounds is upper-bounded in terms of the parameter value alone.
Cite as
Ralph Bottesch. Relativization and Interactive Proof Systems in Parameterized Complexity Theory. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bottesch:LIPIcs.IPEC.2017.9,
author = {Bottesch, Ralph},
title = {{Relativization and Interactive Proof Systems in Parameterized Complexity Theory}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {9:1--9:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.9},
URN = {urn:nbn:de:0030-drops-85715},
doi = {10.4230/LIPIcs.IPEC.2017.9},
annote = {Keywords: Parameterized complexity, Relativization, Interactive Proof Systems}
}
Document
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?
Abstract
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c for a fixed integer c>0. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs.
In this article we answer this question by finding two very natural such problems: we prove that VERTEX COVER admits a polynomial kernel on general graphs for any integer c>0, and that DOMINATING SET does not for any integer c>1 even on degenerate graphs, unless NP is a subset of coNP/poly. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for c>2 and an OR-cross-composition for c=2. As existing results imply that DOMINATING SET admits a polynomial kernel on degenerate graphs for c=1, our result provides a dichotomy about the existence of polynomial problems for DOMINATING SET on degenerate graphs with this parameter.
Cite as
Marin Bougeret and Ignasi Sau. How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{bougeret_et_al:LIPIcs.IPEC.2017.10,
author = {Bougeret, Marin and Sau, Ignasi},
title = {{How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {10:1--10:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.10},
URN = {urn:nbn:de:0030-drops-85564},
doi = {10.4230/LIPIcs.IPEC.2017.10},
annote = {Keywords: parameterized complexity, polynomial kernels, structural parameters, treedepth, treewidth, sparse graphs}
}
Document
Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems
Abstract
We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-0.936}) randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.
Cite as
Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{cardinal_et_al:LIPIcs.IPEC.2017.11,
author = {Cardinal, Jean and Nummenpalo, Jerri and Welzl, Emo},
title = {{Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {11:1--11:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.11},
URN = {urn:nbn:de:0030-drops-85459},
doi = {10.4230/LIPIcs.IPEC.2017.11},
annote = {Keywords: Satisfiability, Sampling, Parameterized complexity}
}
Document
Odd Multiway Cut in Directed Acyclic Graphs
Abstract
We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of non-terminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is an extension of the shadow-removal framework for parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.
Cite as
Karthekeyan Chandrasekaran and Sahand Mozaffari. Odd Multiway Cut in Directed Acyclic Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{chandrasekaran_et_al:LIPIcs.IPEC.2017.12,
author = {Chandrasekaran, Karthekeyan and Mozaffari, Sahand},
title = {{Odd Multiway Cut in Directed Acyclic Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {12:1--12:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.12},
URN = {urn:nbn:de:0030-drops-85470},
doi = {10.4230/LIPIcs.IPEC.2017.12},
annote = {Keywords: Odd Multiway Cut, Fixed-Parameter Tractability, Approximation Algorithms}
}
Document
A Fixed-Parameter Perspective on #BIS
Abstract
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHPi_1. It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in #RHPi_1, and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms.
Cite as
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, and John Lapinskas. A Fixed-Parameter Perspective on #BIS. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{curticapean_et_al:LIPIcs.IPEC.2017.13,
author = {Curticapean, Radu and Dell, Holger and Fomin, Fedor V. and Goldberg, Leslie Ann and Lapinskas, John},
title = {{A Fixed-Parameter Perspective on #BIS}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {13:1--13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.13},
URN = {urn:nbn:de:0030-drops-85613},
doi = {10.4230/LIPIcs.IPEC.2017.13},
annote = {Keywords: Approximate counting, parameterised complexity, independent sets}
}
Document
The Dominating Set Problem in Geometric Intersection Graphs
Abstract
We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.
Cite as
Mark de Berg, Sándor Kisfaludi-Bak, and Gerhard Woeginger. The Dominating Set Problem in Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{deberg_et_al:LIPIcs.IPEC.2017.14,
author = {de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Woeginger, Gerhard},
title = {{The Dominating Set Problem in Geometric Intersection Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {14:1--14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.14},
URN = {urn:nbn:de:0030-drops-85538},
doi = {10.4230/LIPIcs.IPEC.2017.14},
annote = {Keywords: dominating set, intersection graph, W-hierarchy}
}
Document
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Abstract
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences X_1,...,X_k of length at most n, the task is to determine the length of the longest common subsequence of X_1,...,X_k that is also strictly increasing. Especially for the case of k=2 (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case.
Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound to rule out O((nL)^{1-epsilon}) time algorithms for LCIS, where L denotes the solution size, and to rule out O(n^{k-epsilon}) time algorithms for k-LCIS. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.
Cite as
Lech Duraj, Marvin Künnemann, and Adam Polak. Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{duraj_et_al:LIPIcs.IPEC.2017.15,
author = {Duraj, Lech and K\"{u}nnemann, Marvin and Polak, Adam},
title = {{Tight Conditional Lower Bounds for Longest Common Increasing Subsequence}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {15:1--15:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.15},
URN = {urn:nbn:de:0030-drops-85706},
doi = {10.4230/LIPIcs.IPEC.2017.15},
annote = {Keywords: fine-grained complexity, combinatorial pattern matching, sequence alignments, parameterized complexity, SETH}
}
Document
K-Best Solutions of MSO Problems on Tree-Decomposable Graphs
Abstract
We show that, for any graph optimization problem in which the feasible solutions can be expressed by a formula in monadic second-order logic describing sets of vertices or edges and in which the goal is to minimize the sum of the weights in the selected sets, we can find the k best solution values for n-vertex graphs of bounded treewidth in time O(n + k log n). In particular, this applies to finding the k shortest simple paths between given vertices in directed graphs of bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.
Cite as
David Eppstein and Denis Kurz. K-Best Solutions of MSO Problems on Tree-Decomposable Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{eppstein_et_al:LIPIcs.IPEC.2017.16,
author = {Eppstein, David and Kurz, Denis},
title = {{K-Best Solutions of MSO Problems on Tree-Decomposable Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {16:1--16:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.16},
URN = {urn:nbn:de:0030-drops-85494},
doi = {10.4230/LIPIcs.IPEC.2017.16},
annote = {Keywords: graph algorithm, k-best, monadic second-order logic, treewidth}
}
Document
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Abstract
Efficient, exact parameterized algorithms are a vibrant theoretical research area. Recent solving competitions, such as the PACE challenge, show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether such algorithms can be built to efficiently solve specific problems in practice, that is, to be competitive with established solving systems. In this paper, we consider Answer Set Programming (ASP), a logic-based declarative modeling and problem solving framework. State-of-the-art ASP solvers generally rely on SAT-based algorithms. In addition, DynASP2, an ASP solver that is based on a classical dynamic programming on tree decompositions, has recently been introduced. DynASP2 outperforms modern ASP solvers when the goal is to count the number of solutions of programs that have small treewidth. However, for quickly finding one solutions, DynASP2 proved uncompetitive. In this paper, we present a new algorithm and implementation, called DynASP2.5, that shows competitive behavior compared to state-of-the-art ASP solvers on problems like Steiner tree for low-treewidth graphs, even when the
task is to find just one solution. Our implementation is based on a novel approach that we call multi-pass dynamic programming.
Cite as
Johannes K. Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. DynASP2.5: Dynamic Programming on Tree Decompositions in Action. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{fichte_et_al:LIPIcs.IPEC.2017.17,
author = {Fichte, Johannes K. and Hecher, Markus and Morak, Michael and Woltran, Stefan},
title = {{DynASP2.5: Dynamic Programming on Tree Decompositions in Action}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {17:1--17:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.17},
URN = {urn:nbn:de:0030-drops-85739},
doi = {10.4230/LIPIcs.IPEC.2017.17},
annote = {Keywords: Parameterized algorithms, Fixed-parameter linear time, Tree decompositions, Multi-pass dynamic programming}
}
Document
Finding Connected Secluded Subgraphs
Abstract
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the traditional P vs NP dichotomy and within parameterized complexity. The Pi-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Pi. For many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Pi-Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the Connected Secluded Pi-Subgraph problem is FPT when parameterized by just t for many important graph properties Pi.
Cite as
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, and Pedro Montealegre. Finding Connected Secluded Subgraphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{golovach_et_al:LIPIcs.IPEC.2017.18,
author = {Golovach, Petr A. and Heggernes, Pinar and Lima, Paloma T. and Montealegre, Pedro},
title = {{Finding Connected Secluded Subgraphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {18:1--18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.18},
URN = {urn:nbn:de:0030-drops-85623},
doi = {10.4230/LIPIcs.IPEC.2017.18},
annote = {Keywords: Secluded subgraph, forbidden subgraphs, parameterized complexity}
}
Document
FO Model Checking of Geometric Graphs
Abstract
Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures – culminating in the FPT algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs. On contrary to that, except the case of locally bounded clique-width only little is currently known about FO model checking of dense classes of graphs or other structures. We study the FO model checking problem for dense graph classes definable by geometric means (intersection and visibility graphs). We obtain new nontrivial FPT results, e.g., for restricted subclasses of circular-arc, circle, box, disk, and polygon-visibility graphs. These results use the FPT algorithm by Gajarský et al. for FO model checking of posets of bounded width. We also complement the tractability results by related hardness reductions.
Cite as
Petr Hlineny, Filip Pokrývka, and Bodhayan Roy. FO Model Checking of Geometric Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hlineny_et_al:LIPIcs.IPEC.2017.19,
author = {Hlineny, Petr and Pokr\'{y}vka, Filip and Roy, Bodhayan},
title = {{FO Model Checking of Geometric Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {19:1--19:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.19},
URN = {urn:nbn:de:0030-drops-85597},
doi = {10.4230/LIPIcs.IPEC.2017.19},
annote = {Keywords: first-order logic, model checking, fixed-parameter tractability, intersection graphs, visibility graphs}
}
Document
Smaller Parameters for Vertex Cover Kernelization
Abstract
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most d, and obtain kernels with O(|X|^{3d+9}) vertices. Our result relies on proving that minimal blocking sets in a d-quasi-forest have size at most d+2. This bound is tight and there is a related lower bound of O(|X|^{d+2-epsilon}) on the bit size of kernels.
In fact, we also get bounds for minimal blocking sets of more general graph classes: For d-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most d vertices, we get the same tight bound of d+2 vertices. For graphs whose connected components each have a vertex cover of cost at most d more than the best fractional vertex cover, which we call d-quasi-integral, we show that minimal blocking sets have size at most 2d+2, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to d-quasi-bipartite and d-quasi-integral graphs. There are lower bounds of O(|X|^{d+2-epsilon}) and O(|X|^{2d+2-epsilon}) for the bit size of such kernels.
Cite as
Eva-Maria C. Hols and Stefan Kratsch. Smaller Parameters for Vertex Cover Kernelization. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{hols_et_al:LIPIcs.IPEC.2017.20,
author = {Hols, Eva-Maria C. and Kratsch, Stefan},
title = {{Smaller Parameters for Vertex Cover Kernelization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {20:1--20:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.20},
URN = {urn:nbn:de:0030-drops-85638},
doi = {10.4230/LIPIcs.IPEC.2017.20},
annote = {Keywords: Vertex Cover, Kernelization, Structural Parameterization}
}
Document
Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width
Abstract
We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give n^O(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H-Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Per- mutation and Circular Permutation graphs, Convex graphs, k-Trapezoid, Circular k-Trapezoid, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k.
Cite as
Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{jaffke_et_al:LIPIcs.IPEC.2017.21,
author = {Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
title = {{Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.21},
URN = {urn:nbn:de:0030-drops-85643},
doi = {10.4230/LIPIcs.IPEC.2017.21},
annote = {Keywords: graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors}
}
Document
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
Abstract
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring.
First, we use a recent technique of finding redundant constraints by representing them as low-degree polynomials, to obtain a kernel of bitsize O(k^(q-1) log k) for q-Coloring parameterized by Vertex Cover for any q >= 3. This size bound is optimal up to k^o(1) factors assuming NP is not a subset of coNP/poly, and improves on the previous-best kernel of size O(k^q). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP is not a subset of coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^(2-e)) for any e > 0. Previously, such a lower bound was only known for coloring with q >= 4 colors.
Cite as
Bart M. P. Jansen and Astrid Pieterse. Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 22:1-22:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.IPEC.2017.22,
author = {Jansen, Bart M. P. and Pieterse, Astrid},
title = {{Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {22:1--22:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.22},
URN = {urn:nbn:de:0030-drops-85500},
doi = {10.4230/LIPIcs.IPEC.2017.22},
annote = {Keywords: graph coloring, kernelization, sparsification}
}
Document
Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
Abstract
The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}?
We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.
Cite as
Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{jansen_et_al:LIPIcs.IPEC.2017.23,
author = {Jansen, Bart M. P. and Pilipczuk, Marcin and Wrochna, Marcin},
title = {{Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {23:1--23:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.23},
URN = {urn:nbn:de:0030-drops-85576},
doi = {10.4230/LIPIcs.IPEC.2017.23},
annote = {Keywords: Turing kernel, long path, k-path, excluded topological minor, modulator}
}
Document
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
Abstract
Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any
partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class.
In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^(k-2) edges in any mimicking network. This nearly matches an upper bound of O(k * 2^(2k)) of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the O(k^2) upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde [JCSS 1998], Khan and Raghavendra [IPL 2014], and Chambers and Eppstein [JGAA 2013].
Cite as
Nikolai Karpov, Marcin Pilipczuk, and Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{karpov_et_al:LIPIcs.IPEC.2017.24,
author = {Karpov, Nikolai and Pilipczuk, Marcin and Zych-Pawlewicz, Anna},
title = {{An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {24:1--24:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.24},
URN = {urn:nbn:de:0030-drops-85603},
doi = {10.4230/LIPIcs.IPEC.2017.24},
annote = {Keywords: mimicking networks, planar graphs}
}
Document
An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization
Abstract
Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs.
In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2^{O(k^2)} is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2^{O(k log k)}n.
Cite as
Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{kobayashi_et_al:LIPIcs.IPEC.2017.25,
author = {Kobayashi, Yasuaki and Ohtsuka, Hiromu and Tamaki, Hisao},
title = {{An Improved Fixed-Parameter Algorithm for One-Page Crossing Minimization}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {25:1--25:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.25},
URN = {urn:nbn:de:0030-drops-85661},
doi = {10.4230/LIPIcs.IPEC.2017.25},
annote = {Keywords: Book Embedding, Fixed-Parameter Tractability, Graph Drawing, Treewidth}
}
Document
Treewidth with a Quantifier Alternation Revisited
Abstract
In this paper we take a closer look at the parameterized complexity of \exists\forall SAT, the prototypical complete problem of the class Sigma_2^p, the second level of the polynomial hierarchy. We provide a number of tight fine-grained bounds on the complexity of this problem and its variants with respect to the most important structural graph parameters. Specifically, we show the following lower bounds (assuming the ETH):
- It is impossible to decide \exists\forall SAT in time less than double-exponential in the input formula's treewidth. More strongly, we establish the same bound with respect to the formula's primal vertex cover, a much more restrictive measure. This lower bound, which matches the performance of known algorithms, shows that the degeneration of the performance of treewidth-based algorithms to a tower of exponentials already begins in problems with one quantifier alternation.
- For the more general \exists\forall CSP problem over a non-boolean domain of size B, there is no algorithm running in time 2^{B^{o(vc)}}, where vc is the input's primal vertex cover.
- \exists\forall SAT is already NP-hard even when the input formula has constant modular treewidth (or clique-width), indicating that dense graph parameters are less useful for problems in Sigma_2^p.
- For the two weighted versions of \exists\forall SAT recently introduced by de Haan and Szeider, called \exists_k\forall SAT and \exists\forall_k SAT, we give tight upper and lower bounds parameterized by treewidth (or primal vertex cover) and the weight k. Interestingly, the complexity of these two problems turns out to be quite different: one is double-exponential in treewidth, while the other is double-exponential in k.
We complement the above negative results by showing a double-exponential FPT algorithm for QBF parameterized by vertex cover, showing that for this parameter the complexity never goes beyond double-exponential, for any number of quantifier alternations.
Cite as
Michael Lampis and Valia Mitsou. Treewidth with a Quantifier Alternation Revisited. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{lampis_et_al:LIPIcs.IPEC.2017.26,
author = {Lampis, Michael and Mitsou, Valia},
title = {{Treewidth with a Quantifier Alternation Revisited}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {26:1--26:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.26},
URN = {urn:nbn:de:0030-drops-85512},
doi = {10.4230/LIPIcs.IPEC.2017.26},
annote = {Keywords: Treewidth, Exponential Time Hypothesis, Quantified SAT}
}
Document
An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs
Abstract
The degeneracy of a graph G is the smallest integer k such that every subgraph of G contains a vertex of degree at most k. Given an n-order k-degenerate graph G, we present an algorithm for enumerating all its maximal cliques. Assuming that c is the number of maximal cliques of G, our algorithm has setup time O(n(k^2+s(k+1))) and enumeration time cO((k+1)f(k+1)) where s(k+1) (resp. f(k+1)) is the preprocessing time (resp. enumeration time) for maximal clique enumeration in a general (k+1)-order graph. This is the first output sensitive algorithm whose enumeration time depends only on the degeneracy of the graph.
Cite as
George Manoussakis. An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 27:1-27:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{manoussakis:LIPIcs.IPEC.2017.27,
author = {Manoussakis, George},
title = {{An Output Sensitive Algorithm for Maximal Clique Enumeration in Sparse Graphs}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {27:1--27:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.27},
URN = {urn:nbn:de:0030-drops-85529},
doi = {10.4230/LIPIcs.IPEC.2017.27},
annote = {Keywords: enumeration algorithms, maximal cliques, k-degenerate graphs}
}
Document
Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem
Abstract
This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.
Cite as
Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt. Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{shang_et_al:LIPIcs.IPEC.2017.28,
author = {Shang, Lei and Garraffa, Michele and Della Croce, Federico and T'Kindt, Vincent},
title = {{Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {28:1--28:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.28},
URN = {urn:nbn:de:0030-drops-85468},
doi = {10.4230/LIPIcs.IPEC.2017.28},
annote = {Keywords: Exact exponential algorithm, Single machine total tardiness, Branch-and-merge}
}
Document
Computing Treewidth on the GPU
Abstract
We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O*(2^n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions.
GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77x) compared to running the same algorithm on the CPU.
Cite as
Tom C. van der Zanden and Hans L. Bodlaender. Computing Treewidth on the GPU. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{vanderzanden_et_al:LIPIcs.IPEC.2017.29,
author = {van der Zanden, Tom C. and Bodlaender, Hans L.},
title = {{Computing Treewidth on the GPU}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.29},
URN = {urn:nbn:de:0030-drops-85671},
doi = {10.4230/LIPIcs.IPEC.2017.29},
annote = {Keywords: treewidth, GPU, GPGPU, exact algorithms, graph algorithms, algorithm engineering}
}
Document
The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration
Abstract
In this article, the Program Committee of the Second Parameterized Algorithms and Computational Experiments challenge (PACE 2017) reports on the second iteration of the PACE challenge. Track A featured the Treewidth problem and Track B the Minimum Fill-In problem. Over 44 participants on 17 teams from 11 countries submitted their implementations to the competition.
Cite as
Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
Copy BibTex To Clipboard
@InProceedings{dell_et_al:LIPIcs.IPEC.2017.30,
author = {Dell, Holger and Komusiewicz, Christian and Talmon, Nimrod and Weller, Mathias},
title = {{The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {30:1--30:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Lokshtanov, Daniel and Nishimura, Naomi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.30},
URN = {urn:nbn:de:0030-drops-85582},
doi = {10.4230/LIPIcs.IPEC.2017.30},
annote = {Keywords: treewidth, minimum fill-in, contest, implementation challenge, FPT}
}