Search Results

Documents authored by Reidl, Felix

Document
DOI: 10.4230/LIPIcs.SWAT.2024.8
Correlation Clustering with Vertex Splitting

Authors: Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We explore CLUSTER EDITING and its generalization CORRELATION CLUSTERING with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both problems are NP-hard, yet they exhibit significant differences in terms of parameterized complexity and approximability. For CLUSTER EDITING WITH PERMISSIVE VERTEX SPLITTING, we show a polynomial kernel when parameterized by the solution size and develop a polynomial-time 7-approximation. In the case of CORRELATION CLUSTERING, we establish para-NP-hardness when parameterized by the solution size and demonstrate that computing an n^{1-ε}-approximation is NP-hard for any constant ε > 0. Additionally, we extend an established link between CORRELATION CLUSTERING and MULTICUT to the setting with permissive vertex splits.
Cite as

Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan. Correlation Clustering with Vertex Splitting. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SWAT.2024.8,
  author =	{Bentert, Matthias and Crane, Alex and Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and Sullivan, Blair D.},
  title =	{{Correlation Clustering with Vertex Splitting}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8},
  URN =		{urn:nbn:de:0030-drops-200483},
  doi =		{10.4230/LIPIcs.SWAT.2024.8},
  annote =	{Keywords: graph modification, cluster editing, overlapping clustering, approximation, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.14
Computing Complexity Measures of Degenerate Graphs

Authors: Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl

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

Abstract
We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time O(d2^dn), afterwards queries can be computed efficiently using fast Möbius inversion. This data structure turns out to be useful for a range of tasks, especially for finding bipartite patterns in degenerate graphs, and we outline an efficient algorithm for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(n^c), where c is a parameter of the pattern we call its left covering number. Concrete applications of this algorithm include counting the number of (non-induced) bicliques in linear time, the number of co-matchings in quadratic time, as well as a constant-factor approximation of the ladder index in linear time. Finally, we supplement our theoretical results with several implementations and run experiments on more than 200 real-world datasets - the largest of which has 8 million edges - where we obtain interesting insights into the VC-dimension of real-world networks.
Cite as

Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing Complexity Measures of Degenerate Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.IPEC.2023.14,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Greaves, Patrick and Muzi, Irene and Reidl, Felix},
  title =	{{Computing Complexity Measures of Degenerate Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14},
  URN =		{urn:nbn:de:0030-drops-194333},
  doi =		{10.4230/LIPIcs.IPEC.2023.14},
  annote =	{Keywords: vc-dimension, datastructure, degeneracy, enumerating}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.25
When You Come at the King You Best Not Miss

Authors: Oded Lachish, Felix Reidl, and Chhaya Trehan

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
A tournament is an orientation of a complete graph. We say that a vertex x in a tournament T controls another vertex y if there exists a directed path of length at most two from x to y. A vertex is called a king if it controls every vertex of the tournament. It is well known that every tournament has a king. We follow Shen, Sheng, and Wu [Jian Shen et al., 2003] in investigating the query complexity of finding a king, that is, the number of arcs in T one has to know in order to surely identify at least one vertex as a king. The aforementioned authors showed that one always has to query at least Ω(n^{4/3}) arcs and provided a strategy that queries at most O(n^{3/2}). While this upper bound has not yet been improved for the original problem, [Biswas et al., 2017] proved that with O(n^{4/3}) queries one can identify a semi-king, meaning a vertex which controls at least half of all vertices. Our contribution is a novel strategy which improves upon the number of controlled vertices: using O(n^{4/3} polylog n) queries, we can identify a (1/2+2/17)-king. To achieve this goal we use a novel structural result for tournaments.
Cite as

Oded Lachish, Felix Reidl, and Chhaya Trehan. When You Come at the King You Best Not Miss. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lachish_et_al:LIPIcs.FSTTCS.2022.25,
  author =	{Lachish, Oded and Reidl, Felix and Trehan, Chhaya},
  title =	{{When You Come at the King You Best Not Miss}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.25},
  URN =		{urn:nbn:de:0030-drops-174177},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.25},
  annote =	{Keywords: Digraphs, tournaments, kings, query complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.11
A General Kernelization Technique for Domination and Independence Problems in Sparse Classes

Authors: Carl Einarson and Felix Reidl

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

Abstract
We unify and extend previous kernelization techniques in sparse classes [Jochen Alber et al., 2004; Pilipczuk and Siebertz, 2018] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r,c)-Dominating Set, (r,c)-Scattered Set, Total r-Domination, r-Roman Domination, and a problem we call (r,[λ,μ])-Domination (implying a bikernel for r-Perfect Code). At the cost of slightly changing the output graph class our bikernels can be turned into kernels. We also demonstrate how these constructions can be combined to create "multikernels", meaning graphs that represent kernels for multiple problems at once.
Cite as

Carl Einarson and Felix Reidl. A General Kernelization Technique for Domination and Independence Problems in Sparse Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{einarson_et_al:LIPIcs.IPEC.2020.11,
  author =	{Einarson, Carl and Reidl, Felix},
  title =	{{A General Kernelization Technique for Domination and Independence Problems in Sparse Classes}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-133142},
  doi =		{10.4230/LIPIcs.IPEC.2020.11},
  annote =	{Keywords: Dominating Set, Independence, Kernelization, Bounded Expansion}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.40
Domination Above r-Independence: Does Sparseness Help?

Authors: Carl Einarson and Felix Reidl

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

Abstract
Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maximal r-independent set X (a set in which all vertices have pairwise distance at least r+1) along the input graph G which, for r >= 2, lower-bounds the minimum size of any dominating set of G. In the spirit of gap-parameters, we consider a parametrisation by the size of the "residual" set R := V(G) \ N[X]. Our work aims to answer two questions: How does the constant r affect the tractability of the problem and does the restriction to sparse graph classes help here? For the base case r = 2, we find that the problem is paraNP-complete even in apex- and bounded-degree graphs. For r = 3, the problem is W[2]-hard for general graphs but in FPT for nowhere dense classes and it admits a linear kernel for bounded expansion classes. For r >= 4, the parametrisation becomes essentially equivalent to the natural parameter, the size of the dominating set.
Cite as

Carl Einarson and Felix Reidl. Domination Above r-Independence: Does Sparseness Help?. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{einarson_et_al:LIPIcs.MFCS.2019.40,
  author =	{Einarson, Carl and Reidl, Felix},
  title =	{{Domination Above r-Independence: Does Sparseness Help?}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{40:1--40:13},
  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.40},
  URN =		{urn:nbn:de:0030-drops-109840},
  doi =		{10.4230/LIPIcs.MFCS.2019.40},
  annote =	{Keywords: Dominating Set, Above Guarantee, Kernel, Bounded Expansion, Nowhere Dense}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.94
Parameterized Algorithms for Zero Extension and Metric Labelling Problems

Authors: Felix Reidl and Magnus Wahlström

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the problems Zero Extension and Metric Labelling under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, but have previously not received much attention from this area. Depending on the chosen cost function mu, we find that different algorithmic approaches can be applied to design FPT-algorithms: for arbitrary mu we parameterize by the number of edges that cross the cut (not the cost) and show how to solve Zero Extension in time O(|D|^{O(k^2)} n^4 log n) using randomized contractions. We improve this running time with respect to both parameter and input size to O(|D|^{O(k)} m) in the case where mu is a metric. We further show that the problem admits a polynomial sparsifier, that is, a kernel of size O(k^{|D|+1}) that is independent of the metric mu. With the stronger condition that mu is described by the distances of leaves in a tree, we parameterize by a gap parameter (q - p) between the cost of a true solution q and a `discrete relaxation' p and achieve a running time of O(|D|^{q-p} |T|m + |T|phi(n,m)) where T is the size of the tree over which mu is defined and phi(n,m) is the running time of a max-flow computation. We achieve a similar result for the more general Metric Labelling, while also allowing mu to be the distance metric between an arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We expect the methods used in the latter result to have further applications.
Cite as

Felix Reidl and Magnus Wahlström. Parameterized Algorithms for Zero Extension and Metric Labelling Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 94:1-94:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{reidl_et_al:LIPIcs.ICALP.2018.94,
  author =	{Reidl, Felix and Wahlstr\"{o}m, Magnus},
  title =	{{Parameterized Algorithms for Zero Extension and Metric Labelling Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{94:1--94:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.94},
  URN =		{urn:nbn:de:0030-drops-90989},
  doi =		{10.4230/LIPIcs.ICALP.2018.94},
  annote =	{Keywords: FPT, VCSP, cut problem, gap parameter}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.14
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Authors: Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, and Sebastian Siebertz

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

Abstract
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this paper we study two structural properties of these graph classes that are of particular importance in this context, namely the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide. We provide experimental evaluations of several algorithms that approximate these parameters on real-world graphs. On the theoretical side, we provide a new algorithm for uniform quasi-wideness with polynomial size guarantees in graph classes of bounded expansion and show a lower bound indicating that the guarantees of this algorithm are close to optimal in graph classes with fixed excluded minor.
Cite as

Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, and Sebastian Siebertz. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nadara_et_al:LIPIcs.SEA.2018.14,
  author =	{Nadara, Wojciech and Pilipczuk, Marcin and Rabinovich, Roman and Reidl, Felix and Siebertz, Sebastian},
  title =	{{Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{14:1--14:16},
  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.14},
  URN =		{urn:nbn:de:0030-drops-89493},
  doi =		{10.4230/LIPIcs.SEA.2018.14},
  annote =	{Keywords: Empirical Evaluation of Algorithms, Sparse Graph Classes, Generalized Coloring Numbers, Uniform Quasi-Wideness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.79
Being Even Slightly Shallow Makes Life Hard

Authors: Irene Muzi, Michael P. O'Brien, Felix Reidl, and Blair D. Sullivan

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We study the computational complexity of identifying dense substructures, namely r/2-shallow topological minors and r-subdivisions. Of particular interest is the case r = 1, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. In the following, we provide a negative answer: Dense r/2-Shallow Topological Minor and Dense r-Subdivsion are already NP-hard for r = 1 in very sparse graphs. Further, they do not admit algorithms with running time 2^(o(tw^2)) n^O(1) when parameterized by the treewidth of the input graph for r > 2 unless ETH fails.
Cite as

Irene Muzi, Michael P. O'Brien, Felix Reidl, and Blair D. Sullivan. Being Even Slightly Shallow Makes Life Hard. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{muzi_et_al:LIPIcs.MFCS.2017.79,
  author =	{Muzi, Irene and O'Brien, Michael P. and Reidl, Felix and Sullivan, Blair D.},
  title =	{{Being Even Slightly Shallow Makes Life Hard}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.79},
  URN =		{urn:nbn:de:0030-drops-81257},
  doi =		{10.4230/LIPIcs.MFCS.2017.79},
  annote =	{Keywords: Topological minors, NP Completeness, Treewidth, ETH, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.47
Path-Contractions, Edge Deletions and Connectivity Preservation

Authors: Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström

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

Abstract
We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertexdeletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed in [Bang-Jensen and Yeo, Discrete Applied Math 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable (FPT) and we provide an FPT algorithm that solves Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivitypreservation constraints in the parameterized setting.
Cite as

Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström. Path-Contractions, Edge Deletions and Connectivity Preservation. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gutin_et_al:LIPIcs.ESA.2017.47,
  author =	{Gutin, Gregory and Ramanujan, M. S. and Reidl, Felix and Wahlstr\"{o}m, Magnus},
  title =	{{Path-Contractions, Edge Deletions and Connectivity Preservation}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{47:1--47:13},
  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.47},
  URN =		{urn:nbn:de:0030-drops-78270},
  doi =		{10.4230/LIPIcs.ESA.2017.47},
  annote =	{Keywords: connectivity, strong connectivity, vertex deletion, arc contraction}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.58
k-Distinct In- and Out-Branchings in Digraphs

Authors: Gregory Gutin, Felix Reidl, and Magnus Wahlström

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

Abstract
An out-branching and an in-branching of a digraph D are called k-distinct if each of them has k arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraph D has k-distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized by k. They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root. By linking the two problems with the problem of whether a digraph has an out-branching with at least k leaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition called the rooted cut decomposition and using it we prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs. We believe that the rooted cut decomposition will be useful for obtaining other results on digraphs.
Cite as

Gregory Gutin, Felix Reidl, and Magnus Wahlström. k-Distinct In- and Out-Branchings in Digraphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gutin_et_al:LIPIcs.ICALP.2017.58,
  author =	{Gutin, Gregory and Reidl, Felix and Wahlstr\"{o}m, Magnus},
  title =	{{k-Distinct In- and Out-Branchings in Digraphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.58},
  URN =		{urn:nbn:de:0030-drops-73788},
  doi =		{10.4230/LIPIcs.ICALP.2017.58},
  annote =	{Keywords: Digraphs, Branchings, Decompositions, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.31
Kernelization and Sparseness: the Case of Dominating Set

Authors: Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
Cite as

Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.STACS.2016.31,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath},
  title =	{{Kernelization and Sparseness: the Case of Dominating Set}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.31},
  URN =		{urn:nbn:de:0030-drops-57327},
  doi =		{10.4230/LIPIcs.STACS.2016.31},
  annote =	{Keywords: kernelization, dominating set, bounded expansion, nowhere dense}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.402
Fast Biclustering by Dual Parameterization

Authors: Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time O(2^{3*sqrt(pk)} + n + m) for p-Starforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for a fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.
Cite as

Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdar. Fast Biclustering by Dual Parameterization. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 402-413, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.IPEC.2015.402,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Sikdar, Somnath},
  title =	{{Fast Biclustering by Dual Parameterization}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{402--413},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.402},
  URN =		{urn:nbn:de:0030-drops-56004},
  doi =		{10.4230/LIPIcs.IPEC.2015.402},
  annote =	{Keywords: graph editing, subexponential algorithms, parameterized complexity}
}
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