Search Results

Documents authored by Knop, Dusan

Found 2 Possible Name Variants:

Knop, Dusan

Document
DOI: 10.4230/LIPIcs.MFCS.2024.29
Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra

Authors: Václav Blažej, Dušan Knop, Jan Pokorný, and Šimon Schierreich

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In the Equitable Connected Partition (ECP for short) problem, we are given a graph G = (V,E) together with an integer p ∈ ℕ, and our goal is to find a partition of V into p parts such that each part induces a connected sub-graph of G and the size of each two parts differs by at most 1. On the one hand, the problem is known to be NP-hard in general and W[1]-hard with respect to the path-width, the feedback-vertex set, and the number of parts p combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number. In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the 4-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the 3-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as N-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra.
Cite as

Václav Blažej, Dušan Knop, Jan Pokorný, and Šimon Schierreich. Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.MFCS.2024.29,
  author =	{Bla\v{z}ej, V\'{a}clav and Knop, Du\v{s}an and Pokorn\'{y}, Jan and Schierreich, \v{S}imon},
  title =	{{Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.29},
  URN =		{urn:nbn:de:0030-drops-205857},
  doi =		{10.4230/LIPIcs.MFCS.2024.29},
  annote =	{Keywords: Equitable Connected Partition, structural parameters, fixed-parameter tractability, N-fold integer programming, tree-width, shrub-depth, modular-width}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.7
Treewidth Is NP-Complete on Cubic Graphs

Authors: Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.
Cite as

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. Treewidth Is NP-Complete on Cubic Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.7,
  author =	{Bodlaender, Hans L. and Bonnet, \'{E}douard and Jaffke, Lars and Knop, Du\v{s}an and Lima, Paloma T. and Milani\v{c}, Martin and Ordyniak, Sebastian and Pandey, Sukanya and Such\'{y}, Ond\v{r}ej},
  title =	{{Treewidth Is NP-Complete on Cubic Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7},
  URN =		{urn:nbn:de:0030-drops-194263},
  doi =		{10.4230/LIPIcs.IPEC.2023.7},
  annote =	{Keywords: Treewidth, cubic graphs, degree, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.22
On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors: Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
Cite as

Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ESA.2022.22,
  author =	{Bla\v{z}ej, V\'{a}clav and Choudhary, Pratibha and Knop, Du\v{s}an and Schierreich, \v{S}imon and Such\'{y}, Ond\v{r}ej and Valla, Tom\'{a}\v{s}},
  title =	{{On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.22},
  URN =		{urn:nbn:de:0030-drops-169600},
  doi =		{10.4230/LIPIcs.ESA.2022.22},
  annote =	{Keywords: Traveling Salesperson, Subset TSP, Waypoint Routing, Kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.73
Scheduling Kernels via Configuration LP

Authors: Dušan Knop and Martin Koutecký

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time p_max has a kernelization yielding a reduced instance whose size is exponential in p_max. Can this be reduced to polynomial in p_max? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series of steps, until its encoding length is polynomial in the parameters. Then, we show that huge N-fold IP is in NP, which implies that there is a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our "conditional kernel" provides new insight.
Cite as

Dušan Knop and Martin Koutecký. Scheduling Kernels via Configuration LP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.ESA.2022.73,
  author =	{Knop, Du\v{s}an and Kouteck\'{y}, Martin},
  title =	{{Scheduling Kernels via Configuration LP}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.73},
  URN =		{urn:nbn:de:0030-drops-170118},
  doi =		{10.4230/LIPIcs.ESA.2022.73},
  annote =	{Keywords: Scheduling, Kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.8
Recognizing Proper Tree-Graphs

Authors: Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.
Cite as

Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop. Recognizing Proper Tree-Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.IPEC.2020.8,
  author =	{Chaplick, Steven and Golovach, Petr A. and Hartmann, Tim A. and Knop, Du\v{s}an},
  title =	{{Recognizing Proper Tree-Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.8},
  URN =		{urn:nbn:de:0030-drops-133118},
  doi =		{10.4230/LIPIcs.IPEC.2020.8},
  annote =	{Keywords: intersection graphs, H-graphs, recognition, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.16
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Authors: Radek Hušek, Dušan Knop, and Tomáš Masařk

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).
Cite as

Radek Hušek, Dušan Knop, and Tomáš Masařk. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{husek_et_al:LIPIcs.IPEC.2020.16,
  author =	{Hu\v{s}ek, Radek and Knop, Du\v{s}an and Masa\v{r}k, Tom\'{a}\v{s}},
  title =	{{Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.16},
  URN =		{urn:nbn:de:0030-drops-133193},
  doi =		{10.4230/LIPIcs.IPEC.2020.16},
  annote =	{Keywords: Steiner tree, approximation, star contractions, minimum spanning tree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.36
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

Authors: Matthias Bentert, Klaus Heeger, and Dušan Knop

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
Cite as

Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ISAAC.2020.36,
  author =	{Bentert, Matthias and Heeger, Klaus and Knop, Du\v{s}an},
  title =	{{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36},
  URN =		{urn:nbn:de:0030-drops-133800},
  doi =		{10.4230/LIPIcs.ISAAC.2020.36},
  annote =	{Keywords: Edge-disjoint paths, pathwidth, feedback vertex number}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.44
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

Authors: Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier

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

Abstract
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we "only" ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.
Cite as

Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bredereck_et_al:LIPIcs.ISAAC.2019.44,
  author =	{Bredereck, Robert and Heeger, Klaus and Knop, Du\v{s}an and Niedermeier, Rolf},
  title =	{{Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{44:1--44:14},
  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.44},
  URN =		{urn:nbn:de:0030-drops-115406},
  doi =		{10.4230/LIPIcs.ISAAC.2019.44},
  annote =	{Keywords: Stable matching, acceptability graph, fixed-parameter tractability, W\lbrack1\rbrack-hardness, treewidth, treedepth, tree-cut width, feedback set numbers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.33
Parameterized Complexity of Fair Vertex Evaluation Problems

Authors: Dušan Knop, Tomáš Masařík, and Tomáš Toufar

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

Abstract
A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula. In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.
Cite as

Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.MFCS.2019.33,
  author =	{Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s}},
  title =	{{Parameterized Complexity of Fair Vertex Evaluation Problems}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{33:1--33:16},
  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.33},
  URN =		{urn:nbn:de:0030-drops-109775},
  doi =		{10.4230/LIPIcs.MFCS.2019.33},
  annote =	{Keywords: Fair objective, metatheorem, fair vertex cover, twin cover, modular width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.25
Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Authors: Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H subseteq G of the minimum cost such that there is a directed path from s to t in H for all st in A(R). It is known that the problem can be solved in time |V(G)|^{O(|A(R)|)} [Feldman and Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|^{o(|A(R)|)} even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|^{o(q)}, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that Directed Steiner Network is solvable in time f(q)* |V(G)|^{O(c_g * q)}, where c_g is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(q)* |V(G)|^{o(q^2/ log q)} algorithm for any function f for the problem on general graphs, unless ETH fails.
Cite as

Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.STACS.2019.25,
  author =	{Eiben, Eduard and Knop, Du\v{s}an and Panolan, Fahad and Such\'{y}, Ond\v{r}ej},
  title =	{{Complexity of the Steiner Network Problem with Respect to the Number of Terminals}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.25},
  URN =		{urn:nbn:de:0030-drops-102642},
  doi =		{10.4230/LIPIcs.STACS.2019.25},
  annote =	{Keywords: Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.44
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Authors: Dušan Knop, Michał Pilipczuk, and Marcin Wrochna

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small. Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. We prove that for {0,1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2^{o(k log k)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018]. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter {dual treedepth} of the matrix A, denoted td_D(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and {b} are in {-1,0,1}, the existence of an algorithm with running time 2^{2^o(td_D(A))} * (k+l)^O(1) would contradict the ETH.
Cite as

Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.STACS.2019.44,
  author =	{Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin},
  title =	{{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.44},
  URN =		{urn:nbn:de:0030-drops-102831},
  doi =		{10.4230/LIPIcs.STACS.2019.44},
  annote =	{Keywords: integer linear programming, fixed-parameter tractability, ETH}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.21
Integer Programming in Parameterized Complexity: Three Miniatures

Authors: Tomás Gavenciak, Dusan Knop, and Martin Koutecký

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k) poly(n). We focus on: - Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. - Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. - Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, and Max-q-Cut by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.
Cite as

Tomás Gavenciak, Dusan Knop, and Martin Koutecký. Integer Programming in Parameterized Complexity: Three Miniatures. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gavenciak_et_al:LIPIcs.IPEC.2018.21,
  author =	{Gavenciak, Tom\'{a}s and Knop, Dusan and Kouteck\'{y}, Martin},
  title =	{{Integer Programming in Parameterized Complexity: Three Miniatures}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.21},
  URN =		{urn:nbn:de:0030-drops-102225},
  doi =		{10.4230/LIPIcs.IPEC.2018.21},
  annote =	{Keywords: graph coloring, parameterized complexity, integer linear programming, integer convex programming}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.18
Target Set Selection in Dense Graph Classes

Authors: Pavel Dvorák, Dusan Knop, and Tomás Toufar

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.
Cite as

Pavel Dvorák, Dusan Knop, and Tomás Toufar. Target Set Selection in Dense Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2018.18,
  author =	{Dvor\'{a}k, Pavel and Knop, Dusan and Toufar, Tom\'{a}s},
  title =	{{Target Set Selection in Dense Graph Classes}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.18},
  URN =		{urn:nbn:de:0030-drops-99666},
  doi =		{10.4230/LIPIcs.ISAAC.2018.18},
  annote =	{Keywords: parameterized complexity, target set selection, dense graphs}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.10
Evaluating and Tuning n-fold Integer Programming

Authors: Katerina Altmanová, Dusan Knop, and Martin Koutecký

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Programming, 2013] showed an algorithm with runtime a^{O(rst + r^2s)} n^3, where a is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements which make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a "best" step, while finding only an "approximatelly best" step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n^3 to n^2 log n which yields the currently asymptotically fastest algorithm for n-fold IP. Finally, we tested the behavior of the algorithm with various values of the tuning parameter and different strategies of finding improving steps. First, we show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior. Second, our new strategy for finding "approximatelly best" steps wildly outperforms the original construction.
Cite as

Katerina Altmanová, Dusan Knop, and Martin Koutecký. Evaluating and Tuning n-fold Integer Programming. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{altmanova_et_al:LIPIcs.SEA.2018.10,
  author =	{Altmanov\'{a}, Katerina and Knop, Dusan and Kouteck\'{y}, Martin},
  title =	{{Evaluating and Tuning n-fold Integer Programming}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89454},
  doi =		{10.4230/LIPIcs.SEA.2018.10},
  annote =	{Keywords: n-fold integer programming, integer programming, analysis of algorithms, primal heuristic, local search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.26
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Authors: Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý

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

Abstract
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For neither of these an EPAS is likely to exist for the studied parameter: for Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
Cite as

Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2018.26,
  author =	{Dvor\'{a}k, Pavel and Feldmann, Andreas Emil and Knop, Du\v{s}an and Masar{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s} and Vesel\'{y}, Pavel},
  title =	{{Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{26:1--26: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.26},
  URN =		{urn:nbn:de:0030-drops-85158},
  doi =		{10.4230/LIPIcs.STACS.2018.26},
  annote =	{Keywords: Steiner Tree, Steiner Forest, Approximation Algorithms, Parameterized Algorithms, Lossy Kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.54
Combinatorial n-fold Integer Programming and Applications

Authors: Dusan Knop, Martin Koutecky, and Matthias Mnich

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra allows to solve ILPs in time that is exponential only in the dimension of the program. That algorithm therefore became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, it was discovered that in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often doubly-exponential in the parameter, and second, an ILP formulation in small dimension can not easily express problems which involve many different costs. Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to a few representative problems like Closest String, Swap Bribery, Weighted Set Multicover, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs an existence of an augmenting step implies an existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
Cite as

Dusan Knop, Martin Koutecky, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.ESA.2017.54,
  author =	{Knop, Dusan and Koutecky, Martin and Mnich, Matthias},
  title =	{{Combinatorial n-fold Integer Programming and Applications}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.54},
  URN =		{urn:nbn:de:0030-drops-78616},
  doi =		{10.4230/LIPIcs.ESA.2017.54},
  annote =	{Keywords: integer programming, closest strings, fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.46
Voting and Bribing in Single-Exponential Time

Authors: Dusan Knop, Martin Koutecký, and Matthias Mnich

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count for a candidate. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized of R-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
Cite as

Dusan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.STACS.2017.46,
  author =	{Knop, Dusan and Kouteck\'{y}, Martin and Mnich, Matthias},
  title =	{{Voting and Bribing in Single-Exponential Time}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert 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.2017.46},
  URN =		{urn:nbn:de:0030-drops-69885},
  doi =		{10.4230/LIPIcs.STACS.2017.46},
  annote =	{Keywords: Parameterized algorithm, swap bribery, n-fold integer programming}
}

Knop, Dušan

Document
DOI: 10.4230/LIPIcs.MFCS.2024.29
Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra

Authors: Václav Blažej, Dušan Knop, Jan Pokorný, and Šimon Schierreich

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In the Equitable Connected Partition (ECP for short) problem, we are given a graph G = (V,E) together with an integer p ∈ ℕ, and our goal is to find a partition of V into p parts such that each part induces a connected sub-graph of G and the size of each two parts differs by at most 1. On the one hand, the problem is known to be NP-hard in general and W[1]-hard with respect to the path-width, the feedback-vertex set, and the number of parts p combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number. In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the 4-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the 3-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as N-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra.
Cite as

Václav Blažej, Dušan Knop, Jan Pokorný, and Šimon Schierreich. Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.MFCS.2024.29,
  author =	{Bla\v{z}ej, V\'{a}clav and Knop, Du\v{s}an and Pokorn\'{y}, Jan and Schierreich, \v{S}imon},
  title =	{{Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.29},
  URN =		{urn:nbn:de:0030-drops-205857},
  doi =		{10.4230/LIPIcs.MFCS.2024.29},
  annote =	{Keywords: Equitable Connected Partition, structural parameters, fixed-parameter tractability, N-fold integer programming, tree-width, shrub-depth, modular-width}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.7
Treewidth Is NP-Complete on Cubic Graphs

Authors: Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.
Cite as

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. Treewidth Is NP-Complete on Cubic Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.7,
  author =	{Bodlaender, Hans L. and Bonnet, \'{E}douard and Jaffke, Lars and Knop, Du\v{s}an and Lima, Paloma T. and Milani\v{c}, Martin and Ordyniak, Sebastian and Pandey, Sukanya and Such\'{y}, Ond\v{r}ej},
  title =	{{Treewidth Is NP-Complete on Cubic Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7},
  URN =		{urn:nbn:de:0030-drops-194263},
  doi =		{10.4230/LIPIcs.IPEC.2023.7},
  annote =	{Keywords: Treewidth, cubic graphs, degree, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.22
On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors: Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
Cite as

Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ESA.2022.22,
  author =	{Bla\v{z}ej, V\'{a}clav and Choudhary, Pratibha and Knop, Du\v{s}an and Schierreich, \v{S}imon and Such\'{y}, Ond\v{r}ej and Valla, Tom\'{a}\v{s}},
  title =	{{On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.22},
  URN =		{urn:nbn:de:0030-drops-169600},
  doi =		{10.4230/LIPIcs.ESA.2022.22},
  annote =	{Keywords: Traveling Salesperson, Subset TSP, Waypoint Routing, Kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.73
Scheduling Kernels via Configuration LP

Authors: Dušan Knop and Martin Koutecký

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time p_max has a kernelization yielding a reduced instance whose size is exponential in p_max. Can this be reduced to polynomial in p_max? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series of steps, until its encoding length is polynomial in the parameters. Then, we show that huge N-fold IP is in NP, which implies that there is a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our "conditional kernel" provides new insight.
Cite as

Dušan Knop and Martin Koutecký. Scheduling Kernels via Configuration LP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.ESA.2022.73,
  author =	{Knop, Du\v{s}an and Kouteck\'{y}, Martin},
  title =	{{Scheduling Kernels via Configuration LP}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.73},
  URN =		{urn:nbn:de:0030-drops-170118},
  doi =		{10.4230/LIPIcs.ESA.2022.73},
  annote =	{Keywords: Scheduling, Kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.8
Recognizing Proper Tree-Graphs

Authors: Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.
Cite as

Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop. Recognizing Proper Tree-Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.IPEC.2020.8,
  author =	{Chaplick, Steven and Golovach, Petr A. and Hartmann, Tim A. and Knop, Du\v{s}an},
  title =	{{Recognizing Proper Tree-Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.8},
  URN =		{urn:nbn:de:0030-drops-133118},
  doi =		{10.4230/LIPIcs.IPEC.2020.8},
  annote =	{Keywords: intersection graphs, H-graphs, recognition, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.16
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

Authors: Radek Hušek, Dušan Knop, and Tomáš Masařk

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).
Cite as

Radek Hušek, Dušan Knop, and Tomáš Masařk. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{husek_et_al:LIPIcs.IPEC.2020.16,
  author =	{Hu\v{s}ek, Radek and Knop, Du\v{s}an and Masa\v{r}k, Tom\'{a}\v{s}},
  title =	{{Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.16},
  URN =		{urn:nbn:de:0030-drops-133193},
  doi =		{10.4230/LIPIcs.IPEC.2020.16},
  annote =	{Keywords: Steiner tree, approximation, star contractions, minimum spanning tree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.36
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

Authors: Matthias Bentert, Klaus Heeger, and Dušan Knop

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
Cite as

Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ISAAC.2020.36,
  author =	{Bentert, Matthias and Heeger, Klaus and Knop, Du\v{s}an},
  title =	{{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36},
  URN =		{urn:nbn:de:0030-drops-133800},
  doi =		{10.4230/LIPIcs.ISAAC.2020.36},
  annote =	{Keywords: Edge-disjoint paths, pathwidth, feedback vertex number}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.44
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

Authors: Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier

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

Abstract
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we "only" ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.
Cite as

Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bredereck_et_al:LIPIcs.ISAAC.2019.44,
  author =	{Bredereck, Robert and Heeger, Klaus and Knop, Du\v{s}an and Niedermeier, Rolf},
  title =	{{Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{44:1--44:14},
  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.44},
  URN =		{urn:nbn:de:0030-drops-115406},
  doi =		{10.4230/LIPIcs.ISAAC.2019.44},
  annote =	{Keywords: Stable matching, acceptability graph, fixed-parameter tractability, W\lbrack1\rbrack-hardness, treewidth, treedepth, tree-cut width, feedback set numbers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.33
Parameterized Complexity of Fair Vertex Evaluation Problems

Authors: Dušan Knop, Tomáš Masařík, and Tomáš Toufar

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

Abstract
A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula. In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one. Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.
Cite as

Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.MFCS.2019.33,
  author =	{Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s}},
  title =	{{Parameterized Complexity of Fair Vertex Evaluation Problems}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{33:1--33:16},
  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.33},
  URN =		{urn:nbn:de:0030-drops-109775},
  doi =		{10.4230/LIPIcs.MFCS.2019.33},
  annote =	{Keywords: Fair objective, metatheorem, fair vertex cover, twin cover, modular width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.25
Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Authors: Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H subseteq G of the minimum cost such that there is a directed path from s to t in H for all st in A(R). It is known that the problem can be solved in time |V(G)|^{O(|A(R)|)} [Feldman and Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|^{o(|A(R)|)} even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|^{o(q)}, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that Directed Steiner Network is solvable in time f(q)* |V(G)|^{O(c_g * q)}, where c_g is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(q)* |V(G)|^{o(q^2/ log q)} algorithm for any function f for the problem on general graphs, unless ETH fails.
Cite as

Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.STACS.2019.25,
  author =	{Eiben, Eduard and Knop, Du\v{s}an and Panolan, Fahad and Such\'{y}, Ond\v{r}ej},
  title =	{{Complexity of the Steiner Network Problem with Respect to the Number of Terminals}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.25},
  URN =		{urn:nbn:de:0030-drops-102642},
  doi =		{10.4230/LIPIcs.STACS.2019.25},
  annote =	{Keywords: Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.44
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Authors: Dušan Knop, Michał Pilipczuk, and Marcin Wrochna

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small. Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. We prove that for {0,1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2^{o(k log k)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018]. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter {dual treedepth} of the matrix A, denoted td_D(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and {b} are in {-1,0,1}, the existence of an algorithm with running time 2^{2^o(td_D(A))} * (k+l)^O(1) would contradict the ETH.
Cite as

Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.STACS.2019.44,
  author =	{Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin},
  title =	{{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.44},
  URN =		{urn:nbn:de:0030-drops-102831},
  doi =		{10.4230/LIPIcs.STACS.2019.44},
  annote =	{Keywords: integer linear programming, fixed-parameter tractability, ETH}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.21
Integer Programming in Parameterized Complexity: Three Miniatures

Authors: Tomás Gavenciak, Dusan Knop, and Martin Koutecký

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k) poly(n). We focus on: - Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. - Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. - Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, and Max-q-Cut by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.
Cite as

Tomás Gavenciak, Dusan Knop, and Martin Koutecký. Integer Programming in Parameterized Complexity: Three Miniatures. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gavenciak_et_al:LIPIcs.IPEC.2018.21,
  author =	{Gavenciak, Tom\'{a}s and Knop, Dusan and Kouteck\'{y}, Martin},
  title =	{{Integer Programming in Parameterized Complexity: Three Miniatures}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.21},
  URN =		{urn:nbn:de:0030-drops-102225},
  doi =		{10.4230/LIPIcs.IPEC.2018.21},
  annote =	{Keywords: graph coloring, parameterized complexity, integer linear programming, integer convex programming}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.18
Target Set Selection in Dense Graph Classes

Authors: Pavel Dvorák, Dusan Knop, and Tomás Toufar

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.
Cite as

Pavel Dvorák, Dusan Knop, and Tomás Toufar. Target Set Selection in Dense Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2018.18,
  author =	{Dvor\'{a}k, Pavel and Knop, Dusan and Toufar, Tom\'{a}s},
  title =	{{Target Set Selection in Dense Graph Classes}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.18},
  URN =		{urn:nbn:de:0030-drops-99666},
  doi =		{10.4230/LIPIcs.ISAAC.2018.18},
  annote =	{Keywords: parameterized complexity, target set selection, dense graphs}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.10
Evaluating and Tuning n-fold Integer Programming

Authors: Katerina Altmanová, Dusan Knop, and Martin Koutecký

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Programming, 2013] showed an algorithm with runtime a^{O(rst + r^2s)} n^3, where a is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements which make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a "best" step, while finding only an "approximatelly best" step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n^3 to n^2 log n which yields the currently asymptotically fastest algorithm for n-fold IP. Finally, we tested the behavior of the algorithm with various values of the tuning parameter and different strategies of finding improving steps. First, we show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior. Second, our new strategy for finding "approximatelly best" steps wildly outperforms the original construction.
Cite as

Katerina Altmanová, Dusan Knop, and Martin Koutecký. Evaluating and Tuning n-fold Integer Programming. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{altmanova_et_al:LIPIcs.SEA.2018.10,
  author =	{Altmanov\'{a}, Katerina and Knop, Dusan and Kouteck\'{y}, Martin},
  title =	{{Evaluating and Tuning n-fold Integer Programming}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89454},
  doi =		{10.4230/LIPIcs.SEA.2018.10},
  annote =	{Keywords: n-fold integer programming, integer programming, analysis of algorithms, primal heuristic, local search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.26
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Authors: Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý

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

Abstract
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For neither of these an EPAS is likely to exist for the studied parameter: for Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
Cite as

Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2018.26,
  author =	{Dvor\'{a}k, Pavel and Feldmann, Andreas Emil and Knop, Du\v{s}an and Masar{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s} and Vesel\'{y}, Pavel},
  title =	{{Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{26:1--26: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.26},
  URN =		{urn:nbn:de:0030-drops-85158},
  doi =		{10.4230/LIPIcs.STACS.2018.26},
  annote =	{Keywords: Steiner Tree, Steiner Forest, Approximation Algorithms, Parameterized Algorithms, Lossy Kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.54
Combinatorial n-fold Integer Programming and Applications

Authors: Dusan Knop, Martin Koutecky, and Matthias Mnich

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra allows to solve ILPs in time that is exponential only in the dimension of the program. That algorithm therefore became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, it was discovered that in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often doubly-exponential in the parameter, and second, an ILP formulation in small dimension can not easily express problems which involve many different costs. Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to a few representative problems like Closest String, Swap Bribery, Weighted Set Multicover, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs an existence of an augmenting step implies an existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
Cite as

Dusan Knop, Martin Koutecky, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.ESA.2017.54,
  author =	{Knop, Dusan and Koutecky, Martin and Mnich, Matthias},
  title =	{{Combinatorial n-fold Integer Programming and Applications}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.54},
  URN =		{urn:nbn:de:0030-drops-78616},
  doi =		{10.4230/LIPIcs.ESA.2017.54},
  annote =	{Keywords: integer programming, closest strings, fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.46
Voting and Bribing in Single-Exponential Time

Authors: Dusan Knop, Martin Koutecký, and Matthias Mnich

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count for a candidate. As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized of R-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
Cite as

Dusan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.STACS.2017.46,
  author =	{Knop, Dusan and Kouteck\'{y}, Martin and Mnich, Matthias},
  title =	{{Voting and Bribing in Single-Exponential Time}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert 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.2017.46},
  URN =		{urn:nbn:de:0030-drops-69885},
  doi =		{10.4230/LIPIcs.STACS.2017.46},
  annote =	{Keywords: Parameterized algorithm, swap bribery, n-fold integer programming}
}
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