Search Results

Documents authored by Sommer, Frank

Document
DOI: 10.4230/LIPIcs.ESA.2024.102
SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints

Authors: Henning Martin Woydt, Christian Komusiewicz, and Frank Sommer

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the Cardinality-Constrained Maximization (Minimization) problem the input is a universe 𝒰, a function f: 2^{{𝒰}} → ℝ, and an integer k, and the task is to find a set S ⊆ 𝒰 with |S| ≤ k that maximizes (minimizes) f(S). Many well-studied problems such as Facility Location, Partial Dominating Set, Group Closeness Centrality and Euclidean k-Medoid Clustering are special cases of Cardinality-Constrained Maximization (Minimization). All the above-mentioned problems have the diminishing return property, that is, the improvement of adding an element e ∈ 𝒰 to a set S is at least as large as adding e to any superset of S. This property is called submodularity for maximization problems and supermodularity for minimization problems. In this work we develop a new exact branch-and-cut algorithm SubModST for the generic Submodular Cardinality-Constrained Maximization and Supermodular Cardinality-Constrained Minimization. We develop several speed-ups for SubModST and we show their effectiveness on six example problems. We show that SubModST outperforms the state-of-the-art solvers developed by Csókás and Vinkó [J. Glob. Optim. '24] and Uematsu et al. [J. Oper. Res. Soc. Japan '20] for Submodular Cardinality-Constrained Maximization by orders of magnitudes.
Cite as

Henning Martin Woydt, Christian Komusiewicz, and Frank Sommer. SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 102:1-102:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{woydt_et_al:LIPIcs.ESA.2024.102,
  author =	{Woydt, Henning Martin and Komusiewicz, Christian and Sommer, Frank},
  title =	{{SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{102:1--102:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.102},
  URN =		{urn:nbn:de:0030-drops-211730},
  doi =		{10.4230/LIPIcs.ESA.2024.102},
  annote =	{Keywords: Branch-and-Cut, Lazy Evaluations, Facility Location, Group Closeness Centrality, Partial Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.60
On the Complexity of Community-Aware Network Sparsification

Authors: Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

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

Abstract
In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1.
Cite as

Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. On the Complexity of Community-Aware Network Sparsification. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{herrendorf_et_al:LIPIcs.MFCS.2024.60,
  author =	{Herrendorf, Emanuel and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{On the Complexity of Community-Aware Network Sparsification}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{60:1--60:18},
  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.60},
  URN =		{urn:nbn:de:0030-drops-206169},
  doi =		{10.4230/LIPIcs.MFCS.2024.60},
  annote =	{Keywords: parameterized complexity, hypergraph support, above guarantee parameterization, exponential-time-hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.4
On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model

Authors: Matthias Bentert, Jannik Schestag, and Frank Sommer

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

Abstract
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set S of safe edges and a set U of unsafe edges and the task is to find a set T of at most k edges such that T - {u} is connected and spans V for any unsafe edge u ∈ T. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.
Cite as

Matthias Bentert, Jannik Schestag, and Frank Sommer. On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.IPEC.2023.4,
  author =	{Bentert, Matthias and Schestag, Jannik and Sommer, Frank},
  title =	{{On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{4:1--4:12},
  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.4},
  URN =		{urn:nbn:de:0030-drops-194232},
  doi =		{10.4230/LIPIcs.IPEC.2023.4},
  annote =	{Keywords: Flexible graph connectivity, NP-hard problem, parameterized complexity, below-guarantee parameterization, treewidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.42
Covering Many (Or Few) Edges with k Vertices in Sparse Graphs

Authors: Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed α between zero and one we are given a graph and two numbers k ∈ ℕ and t ∈ ℚ. The task is to find a vertex subset S of exactly k vertices that has value at least (resp. at most for minimization) t. Here, the value of a vertex set computes as α times the number of edges with exactly one endpoint in S plus 1-α times the number of edges with both endpoints in S. These two problems generalize many prominent graph problems, such as Densest k-Subgraph, Sparsest k-Subgraph, Partial Vertex Cover, and Max (k,n-k)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max (k,n-k)-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.
Cite as

Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering Many (Or Few) Edges with k Vertices in Sparse Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2022.42,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Nichterlein, Andr\'{e} and Sommer, Frank},
  title =	{{Covering Many (Or Few) Edges with k Vertices in Sparse Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra 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.2022.42},
  URN =		{urn:nbn:de:0030-drops-158525},
  doi =		{10.4230/LIPIcs.STACS.2022.42},
  annote =	{Keywords: Parameterized Complexity, Kernelization, Partial Vertex Cover, Densest k-Subgraph, Max (k,n-k)-Cut, Degeneracy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.35
Essentially Tight Kernels For (Weakly) Closed Graphs

Authors: Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k^𝒪(γ), k^𝒪(γ), and (γk)^𝒪(γ), respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k^o(γ) by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. For Capacitated Vertex Cover, we show that even a kernel of size k^o(c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a problem kernel with 𝒪(ck²) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class 𝒢 admits a kernel of size k^𝒪(γ) when 𝒢 contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.
Cite as

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially Tight Kernels For (Weakly) Closed Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.ISAAC.2021.35,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank},
  title =	{{Essentially Tight Kernels For (Weakly) Closed Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.35},
  URN =		{urn:nbn:de:0030-drops-154681},
  doi =		{10.4230/LIPIcs.ISAAC.2021.35},
  annote =	{Keywords: Fixed-parameter tractability, kernelization, c-closure, weak \gamma-closure, Independent Set, Induced Matching, Connected Vertex Cover, Ramsey numbers, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.20
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs

Authors: Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

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

Abstract
A graph G is weakly γ-closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that |N(u)∩ N(v)| < γ. The weak closure γ(G) of a graph, recently introduced by Fox et al. [SIAM J. Comp. 2020], is the smallest number such that G is weakly γ-closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. [SIAM J. Comp. 2020] on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to γ(G). Moreover, we show that the problem of determining whether a weakly γ-closed graph G has a subgraph on at least k vertices that belongs to a graph class 𝒢 which is closed under taking subgraphs admits a kernel with at most γ k² vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by γ+k where k is the solution size.
Cite as

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.ISAAC.2020.20,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank},
  title =	{{Computing Dense and Sparse Subgraphs of Weakly Closed Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{20:1--20:17},
  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.20},
  URN =		{urn:nbn:de:0030-drops-133646},
  doi =		{10.4230/LIPIcs.ISAAC.2020.20},
  annote =	{Keywords: Fixed-parameter tractability, c-closure, degeneracy, clique relaxations, bicliques, dominating set}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.30
Colored Cut Games

Authors: Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
In a graph G = (V,E) with an edge coloring 𝓁:E → C and two distinguished vertices s and t, a colored (s,t)-cut is a set C̃ ⊆ C such that deleting all edges with some color c ∈ C̃ from G disconnects s and t. Motivated by applications in the design of robust networks, we introduce a family of problems called colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. It is the goal of the attacker to achieve a colored (s,t)-cut and the goal of the defender to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete. We then show that, even on subcubic graphs, colored cut games with a constant number i of alternations are complete for classes in the polynomial hierarchy whose level depends on i. To complete the dichotomy, we show that all colored cut games are polynomial-time solvable on graphs with degree at most two. Finally, we show that all colored cut games admit a polynomial kernel for the parameter k+κ_r where k denotes the total attacker budget and, for any constant r, κ_r is the number of vertex deletions that are necessary to transform G into a graph where the longest path has length at most r. In the case of r = 1, κ₁ is the vertex cover number vc of the input graph and we obtain a kernel with 𝒪(vc²k²) edges. Moreover, we introduce an algorithm solving the most basic colored cut game, Colored (s,t)-Cut, in 2^{vc + k}n^{𝒪(1)} time.
Cite as

Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Colored Cut Games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{morawietz_et_al:LIPIcs.FSTTCS.2020.30,
  author =	{Morawietz, Nils and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Sommer, Frank},
  title =	{{Colored Cut Games}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.30},
  URN =		{urn:nbn:de:0030-drops-132719},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.30},
  annote =	{Keywords: Labeled Cut, Labeled Path, Network Robustness, Kernelization, PSPACE, Polynomial Hierarchy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.65
Exploiting c-Closure in Kernelization Algorithms for Graph Problems

Authors: Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput. '20] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^𝒪(c), that Induced Matching admits a kernel with 𝒪(c⁷ k⁸) vertices, and that Irredundant Set admits a kernel with 𝒪(c^{5/2} k³) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.
Cite as

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.ESA.2020.65,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank},
  title =	{{Exploiting c-Closure in Kernelization Algorithms for Graph Problems}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.65},
  URN =		{urn:nbn:de:0030-drops-129316},
  doi =		{10.4230/LIPIcs.ESA.2020.65},
  annote =	{Keywords: Fixed-parameter tractability, kernelization, c-closure, Dominating Set, Induced Matching, Irredundant Set, Ramsey numbers}
}
Document
DOI: 10.4230/LIPIcs.CPM.2020.17
String Factorizations Under Various Collision Constraints

Authors: Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract
In the NP-hard Equality-Free String Factorization problem, we are given a string S and ask whether S can be partitioned into k factors that are pairwise distinct. We describe a randomized algorithm for Equality-Free String Factorization with running time 2^k⋅ k^{𝒪(1)}+𝒪(n) improving over previous algorithms with running time k^{𝒪(k)}+𝒪(n) [Schmid, TCS 2016; Mincu and Popa, Proc. SOFSEM 2020]. Our algorithm works for the generalization of Equality-Free String Factorization where equality can be replaced by an arbitrary polynomial-time computable equivalence relation on strings. We also consider two factorization problems to which this algorithm does not apply, namely Prefix-Free String Factorization where we ask for a factorization of size k such that no factor is a prefix of another factor and Substring-Free String Factorization where we ask for a factorization of size k such that no factor is a substring of another factor. We show that these two problems are NP-hard as well. Then, we show that Prefix-Free String Factorization with the prefix-free relation is fixed-parameter tractable with respect to k by providing a polynomial problem kernel. Finally, we show a generic ILP formulation for R-Free String Factorization where R is an arbitrary relation on strings. This formulation improves over a previous one for Equality-Free String Factorization in terms of the number of variables.
Cite as

Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. String Factorizations Under Various Collision Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.CPM.2020.17,
  author =	{Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils and Sommer, Frank},
  title =	{{String Factorizations Under Various Collision Constraints}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.17},
  URN =		{urn:nbn:de:0030-drops-121428},
  doi =		{10.4230/LIPIcs.CPM.2020.17},
  annote =	{Keywords: NP-hard problem, fixed-parameter algorithms, collision-aware string partitioning}
}
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