Search Results

Documents authored by Sorge, Manuel

Document
DOI: 10.4230/LIPIcs.ESA.2022.44
Turbocharging Heuristics for Weak Coloring Numbers

Authors: Alexander Dobler, Manuel Sorge, and Anaïs Villedieu

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

Abstract
Bounded expansion and nowhere-dense classes of graphs capture the theoretical tractability for several important algorithmic problems. These classes of graphs can be characterized by the so-called weak coloring numbers of graphs, which generalize the well-known graph invariant degeneracy (also called k-core number). Being NP-hard, weak-coloring numbers were previously computed on real-world graphs mainly via incremental heuristics. We study whether it is feasible to augment such heuristics with exponential-time subprocedures that kick in when a desired upper bound on the weak coloring number is breached. We provide hardness and tractability results on the corresponding computational subproblems. We implemented several of the resulting algorithms and show them to be competitive with previous approaches on a previously studied set of benchmark instances containing 86 graphs with up to 183831 edges. We obtain improved weak coloring numbers for over half of the instances.
Cite as

Alexander Dobler, Manuel Sorge, and Anaïs Villedieu. Turbocharging Heuristics for Weak Coloring Numbers. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.ESA.2022.44,
  author =	{Dobler, Alexander and Sorge, Manuel and Villedieu, Ana\"{i}s},
  title =	{{Turbocharging Heuristics for Weak Coloring Numbers}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{44:1--44:18},
  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.44},
  URN =		{urn:nbn:de:0030-drops-169820},
  doi =		{10.4230/LIPIcs.ESA.2022.44},
  annote =	{Keywords: Structural sparsity, parameterized algorithms, parameterized complexity, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.49
Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings

Authors: Shaohua Li, Marcin Pilipczuk, and Manuel Sorge

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Given a graph G = (V,E) and an integer k, the Cluster Editing problem asks whether we can transform G into a union of vertex-disjoint cliques by at most k modifications (edge deletions or insertions). In this paper, we study the following variant of Cluster Editing. We are given a graph G = (V,E), a packing ℋ of modification-disjoint induced P₃s (no pair of P₃s in H share an edge or non-edge) and an integer 𝓁. The task is to decide whether G can be transformed into a union of vertex-disjoint cliques by at most 𝓁+|H| modifications (edge deletions or insertions). We show that this problem is NP-hard even when 𝓁 = 0 (in which case the problem asks to turn G into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of H) and when each vertex is in at most 23 P₃s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer c such that the problem remains tractable when restricting to packings such that each vertex is in at most c packed P₃s. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect to 𝓁 and we show that the case c = 2 is solvable in |V|^{2𝓁 + O(1)} time.
Cite as

Shaohua Li, Marcin Pilipczuk, and Manuel Sorge. Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.STACS.2021.49,
  author =	{Li, Shaohua and Pilipczuk, Marcin and Sorge, Manuel},
  title =	{{Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.49},
  URN =		{urn:nbn:de:0030-drops-136945},
  doi =		{10.4230/LIPIcs.STACS.2021.49},
  annote =	{Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.37
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth

Authors: Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki

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

Abstract
This year’s Parameterized Algorithms and Computational Experiments challenge (PACE 2020) was devoted to the problem of computing the treedepth of a given graph. Altogether 51 participants from 20 teams, 12 countries and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers and the differences in their performance on our benchmark dataset.
Cite as

Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.IPEC.2020.37,
  author =	{Kowalik, {\L}ukasz and Mucha, Marcin and Nadara, Wojciech and Pilipczuk, Marcin and Sorge, Manuel and Wygocki, Piotr},
  title =	{{The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{37:1--37: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.37},
  URN =		{urn:nbn:de:0030-drops-133404},
  doi =		{10.4230/LIPIcs.IPEC.2020.37},
  annote =	{Keywords: computing treedepth, contest, implementation challenge, FPT}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.59
The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Authors: Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge

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

Abstract
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.
Cite as

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.ISAAC.2020.59,
  author =	{Bellitto, Thomas and Li, Shaohua and Okrasa, Karolina and Pilipczuk, Marcin and Sorge, Manuel},
  title =	{{The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{59:1--59:15},
  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.59},
  URN =		{urn:nbn:de:0030-drops-134036},
  doi =		{10.4230/LIPIcs.ISAAC.2020.59},
  annote =	{Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.28
On Computing Centroids According to the p-Norms of Hamming Distance Vectors

Authors: Jiehua Chen, Danny Hermelin, and Manuel Sorge

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In this paper we consider the p-Norm Hamming Centroid problem which asks to determine whether some given strings have a centroid with a bound on the p-norm of its Hamming distances to the strings. Specifically, given a set S of strings and a real k, we consider the problem of determining whether there exists a string s^* with (sum_{s in S} d^{p}(s^*,s))^(1/p) <=k, where d(,) denotes the Hamming distance metric. This problem has important applications in data clustering and multi-winner committee elections, and is a generalization of the well-known polynomial-time solvable Consensus String (p=1) problem, as well as the NP-hard Closest String (p=infty) problem. Our main result shows that the problem is NP-hard for all fixed rational p > 1, closing the gap for all rational values of p between 1 and infty. Under standard complexity assumptions the reduction also implies that the problem has no 2^o(n+m)-time or 2^o(k^(p/(p+1)))-time algorithm, where m denotes the number of input strings and n denotes the length of each string, for any fixed p > 1. The first bound matches a straightforward brute-force algorithm. The second bound is tight in the sense that for each fixed epsilon > 0, we provide a 2^(k^(p/((p+1))+epsilon))-time algorithm. In the last part of the paper, we complement our hardness result by presenting a fixed-parameter algorithm and a factor-2 approximation algorithm for the problem.
Cite as

Jiehua Chen, Danny Hermelin, and Manuel Sorge. On Computing Centroids According to the p-Norms of Hamming Distance Vectors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2019.28,
  author =	{Chen, Jiehua and Hermelin, Danny and Sorge, Manuel},
  title =	{{On Computing Centroids According to the p-Norms of Hamming Distance Vectors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.28},
  URN =		{urn:nbn:de:0030-drops-111495},
  doi =		{10.4230/LIPIcs.ESA.2019.28},
  annote =	{Keywords: Strings, Clustering, Multiwinner Election, Hamming Distance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.72
Packing Directed Circuits Quarter-Integrally

Authors: Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, and Manuel Sorge

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of k vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size O(k log k). After being known for long as Younger’s conjecture, a similar statement for directed graphs has been proven in 1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof, the dependency of the size of the feedback vertex set on the size of vertex-disjoint cycle packing is not elementary. We show that if we compare the size of a minimum feedback vertex set in a directed graph with quarter-integral cycle packing number, we obtain a polynomial bound. More precisely, we show that if in a directed graph G there is no family of k cycles such that every vertex of G is in at most four of the cycles, then there exists a feedback vertex set in G of size O(k^4). On the way there we prove a more general result about quarter-integral packing of subgraphs of high directed treewidth: for every pair of positive integers a and b, if a directed graph G has directed treewidth Omega(a^6 b^8 log^2(ab)), then one can find in G a family of a subgraphs, each of directed treewidth at least b, such that every vertex of G is in at most four subgraphs.
Cite as

Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, and Manuel Sorge. Packing Directed Circuits Quarter-Integrally. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{masarik_et_al:LIPIcs.ESA.2019.72,
  author =	{Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Muzi, Irene and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Sorge, Manuel},
  title =	{{Packing Directed Circuits Quarter-Integrally}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{72:1--72:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.72},
  URN =		{urn:nbn:de:0030-drops-111938},
  doi =		{10.4230/LIPIcs.ESA.2019.72},
  annote =	{Keywords: Directed graphs, graph algorithms, linkage, Erd\H{o}s–P\'{o}sa property}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.24
Cluster Editing in Multi-Layer and Temporal Graphs

Authors: Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

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

Abstract
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.
Cite as

Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Cluster Editing in Multi-Layer and Temporal Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.24,
  author =	{Chen, Jiehua and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Cluster Editing in Multi-Layer and Temporal Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-99729},
  doi =		{10.4230/LIPIcs.ISAAC.2018.24},
  annote =	{Keywords: Cluster Editing, Temporal Graphs, Multi-Layer Graphs, Fixed-Parameter Algorithms, Polynomial Kernels, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.51
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Authors: Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A fundamental graph problem is to recognize whether the vertex set of a graph G can be bipartitioned into sets A and B such that G[A] and G[B] satisfy properties Pi_A and Pi_B, respectively. This so-called (Pi_A,Pi_B)-Recognition problem generalizes amongst others the recognition of 3-colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can be used to obtain fixed-parameter algorithms for many cases of (Pi_A,Pi_B)-Recognition, as well as several other problems, is the pushing process. For bipartition problems, the process starts with an "almost correct" bipartition (A',B'), and pushes appropriate vertices from A' to B' and vice versa to eventually arrive at a correct bipartition. In this paper, we study whether (Pi_A,Pi_B)-Recognition problems for which the pushing process yields fixed-parameter algorithms also admit polynomial problem kernels. In our study, we focus on the first level above triviality, where Pi_A is the set of P_3-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph G[A], and Pi_B is characterized by a set H of connected forbidden induced subgraphs. We prove that, under the assumption that NP not subseteq coNP/poly, (Pi_A,Pi_B)-Recognition admits a polynomial kernel if and only if H contains a graph of order at most 2. In both the kernelization and the lower bound results, we make crucial use of the pushing process.
Cite as

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.ESA.2018.51,
  author =	{Kanj, Iyad and Komusiewicz, Christian and Sorge, Manuel and van Leeuwen, Erik Jan},
  title =	{{Solving Partition Problems Almost Always Requires Pushing Many Vertices Around}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.51},
  URN =		{urn:nbn:de:0030-drops-95140},
  doi =		{10.4230/LIPIcs.ESA.2018.51},
  annote =	{Keywords: Fixed-parameter algorithms, Kernelization, Vertex-partition problems, Reduction rules, Cross-composition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.35
How Hard Is It to Satisfy (Almost) All Roommates?

Authors: Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion

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

Abstract
The classic Stable Roommates problem (the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners. Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost gamma, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called Min-Block-Pair Stable Roommates, which seeks to find a matching with a minimum number beta of blocking pairs. Our main result is that Egal Stable Roommates parameterized by gamma is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by beta is W[1]-hard, even if the length of each preference list is at most five.
Cite as

Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How Hard Is It to Satisfy (Almost) All Roommates?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2018.35,
  author =	{Chen, Jiehua and Hermelin, Danny and Sorge, Manuel and Yedidsion, Harel},
  title =	{{How Hard Is It to Satisfy (Almost) All Roommates?}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{35:1--35:15},
  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.35},
  URN =		{urn:nbn:de:0030-drops-90398},
  doi =		{10.4230/LIPIcs.ICALP.2018.35},
  annote =	{Keywords: NP-hard problems Data reduction rules Kernelizations Parameterized complexity analysis and algorithmics}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.5
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

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

Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.
Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.14
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs

Authors: Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We consider the recognition problem for two graph classes that generalize split and unipolar graphs, respectively. First, we consider the recognizability of graphs that admit a monopolar partition: a partition of the vertex set into sets A,B such that G[A] is a disjoint union of cliques and G[B] an independent set. If in such a partition G[A] is a single clique, then G is a split graph. We show that in O(2^k * k^3 * (|V(G)| + |E(G)|)) time we can decide whether G admits a monopolar partition (A,B) where G[A] has at most k cliques. This generalizes the linear-time algorithm for recognizing split graphs corresponding to the case when k=1. Second, we consider the recognizability of graphs that admit a 2-subcoloring: a partition of the vertex set into sets A,B such that each of G[A] and G[B] is a disjoint union of cliques. If in such a partition G[A] is a single clique, then G is a unipolar graph. We show that in O(k^(2k+2) * (|V(G)|^2+|V(G)| * |E(G)|)) time we can decide whether G admits a 2-subcoloring (A,B) where G[A] has at most k cliques. This generalizes the polynomial-time algorithm for recognizing unipolar graphs corresponding to the case when k=1. We also show that in O(4^k) time we can decide whether G admits a 2-subcoloring (A,B) where G[A] and G[B] have at most k cliques in total. To obtain the first two results above, we formalize a technique, which we dub inductive recognition, that can be viewed as an adaptation of iterative compression to recognition problems. We believe that the formalization of this technique will prove useful in general for designing parameterized algorithms for recognition problems. Finally, we show that, unless the Exponential Time Hypothesis fails, no subexponential-time algorithms for the above recognition problems exist, and that, unless P=NP, no generic fixed-parameter algorithm exists for the recognizability of graphs whose vertex set can be bipartitioned such that one part is a disjoint union of k cliques.
Cite as

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SWAT.2016.14,
  author =	{Kanj, Iyad and Komusiewicz, Christian and Sorge, Manuel and Jan van Leeuwen, Erik},
  title =	{{Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.14},
  URN =		{urn:nbn:de:0030-drops-60360},
  doi =		{10.4230/LIPIcs.SWAT.2016.14},
  annote =	{Keywords: vertex-partition problems, monopolar graphs, subcolorings, split graphs, unipolar graphs, fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.448
The Parameterized Complexity of the Minimum Shared Edges Problem

Authors: Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. We show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined. We show that MSE is fixed-parameter tractable with respect to p, but does not admit a polynomial-size kernel (unless NP is a subset of coNP/poly). In the proof of the fixed-parameter tractability of MSE parameterized by p, we employ the treewidth reduction technique due to Marx, O'Sullivan, and Razgon [ACM TALG 2013].
Cite as

Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge. The Parameterized Complexity of the Minimum Shared Edges Problem. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 448-462, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.FSTTCS.2015.448,
  author =	{Fluschnik, Till and Kratsch, Stefan and Niedermeier, Rolf and Sorge, Manuel},
  title =	{{The Parameterized Complexity of the Minimum Shared Edges Problem}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{448--462},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.448},
  URN =		{urn:nbn:de:0030-drops-56323},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.448},
  annote =	{Keywords: Parameterized complexity, kernelization, treewidth, treewidth reduction}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.377
On Kernelization and Approximation for the Vector Connectivity Problem

Authors: Stefan Kratsch and Manuel Sorge

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

Abstract
In the Vector Connectivity problem we are given an undirected graph G=(V,E), a demand function phi: V => {0,...,d}, and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex v in V\S has at least phi(v) vertex-disjoint paths to S; this abstractly captures questions about placing servers in a network, or warehouses on a map, relative to demands. The problem is NP-hard already for instances with d=4 (Cicalese et al., Theor. Comput. Sci. 2015), admits a log-factor approximation (Boros et al., Networks 2014), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished 2014). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, i.e., an efficient reduction to an equivalent instance with f(d)k=O(k) vertices. For Vector Connectivity we get a factor opt-approximation and we show that it has no kernelization to size polynomial in k+d unless NP \subseteq coNP/poly, making f(d)\poly(k) optimal for Vector d-Connectivity. Finally, we provide a write-up for fixed-parameter tractability of Vector Connectivity(k) by giving a different algorithm based on matroid intersection.
Cite as

Stefan Kratsch and Manuel Sorge. On Kernelization and Approximation for the Vector Connectivity Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kratsch_et_al:LIPIcs.IPEC.2015.377,
  author =	{Kratsch, Stefan and Sorge, Manuel},
  title =	{{On Kernelization and Approximation for the Vector Connectivity Problem}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{377--388},
  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.377},
  URN =		{urn:nbn:de:0030-drops-55985},
  doi =		{10.4230/LIPIcs.IPEC.2015.377},
  annote =	{Keywords: parameterized complexity, kernelization, approximation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.130
Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems

Authors: René van Bevern, Christian Komusiewicz, and Manuel Sorge

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
We show that any alpha(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(alpha(C))-approximation algorithms for various mixed, windy, and capacitated arc routing problems. Herein, C is the number of weakly-connected components in the subgraph induced by the positive-demand arcs, a number that can be expected to be small in applications. In conjunction with known results, we derive constant-factor approximations if C is in O(log n) and O(log(C)/log(log(C)))-approximations in general.
Cite as

René van Bevern, Christian Komusiewicz, and Manuel Sorge. Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 130-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2015.130,
  author =	{van Bevern, Ren\'{e} and Komusiewicz, Christian and Sorge, Manuel},
  title =	{{Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{130--143},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.130},
  URN =		{urn:nbn:de:0030-drops-54575},
  doi =		{10.4230/OASIcs.ATMOS.2015.130},
  annote =	{Keywords: vehicle routing, transportation, Rural Postman, Chinese Postman, NP- hard problem, parameterized algorithm, combinatorial optimization}
}
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