9 Search Results for "Grüttemeier, Niels"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.25
Parameterized Critical Node Cut Revisited

Authors: Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph G and integers k,x ≥ 0, Critical Node Cut (CNC) asks whether we can delete at most k vertices so that the number of remaining unordered pairs of connected vertices is at most x. CNC generalizes Vertex Cover (the case x = 0) and models tasks in network design, epidemiology, and social network analysis. We comprehensively map the structural parameterized complexity landscape for Critical Node Cut. First, we prove W[1]-hardness for the combined parameter k + fes + Δ + pw, where fes is the feedback edge set number, Δ the maximum degree, and pw the pathwidth of the input graph, respectively. This significantly improves over the known W[1]-hardness for k+tw, where tw denotes the treewidth, and is tight in that tree-depth together with maximum degree trivially yields FPT. Second, we give new positive results. Specifically, we identify three structural parameters-max-leaf number, vertex integrity, and modular-width-that render the problem fixed-parameter tractable, and develop a polynomial-time algorithm for graphs of constant clique-width. Third, leveraging a technique introduced by Lampis [ICALP '14], we develop an FPT approximation scheme that, for any ε > 0, computes a (1+ε)-approximate solution in time (tw / ε)^{𝒪(tw)} n^{𝒪(1)}. Finally, we show that CNC admits no polynomial kernel when parameterized by vertex cover number, unless standard assumptions fail. Together, these results substantially sharpen the known complexity landscape for CNC.
Cite as

Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Critical Node Cut Revisited. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.SWAT.2026.25,
  author =	{Knop, Du\v{s}an and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Critical Node Cut Revisited}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.25},
  URN =		{urn:nbn:de:0030-drops-260617},
  doi =		{10.4230/LIPIcs.SWAT.2026.25},
  annote =	{Keywords: Critical Node Cut, Parameterized Complexity, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.66
A Parameterized-Complexity Framework for Finding Local Optima

Authors: Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood. The traditional frameworks, PLS and the standard algorithm problem, introduced by Johnson, Papadimitriou, and Yannakakis (1988) fail to capture the methodology of local search algorithms: PLS is concerned with finding a local optimum and not with using local search, while the standard algorithm problem restricts each improvement step to follow a fixed pivoting rule. In this work, we introduce a novel formulation of local search which provides a middle ground between these models. In particular, the task is to output not only a local optimum but also a chain of local improvements leading to it. With this framework, we aim to capture the challenge in designing a good pivoting rule. Especially, when combined with the parameterized complexity paradigm, it enables both strong lower bounds and meaningful tractability results. Unlike previous works that combined parameterized complexity with local search, our framework targets the whole task of finding a local optimum and not only a single improvement step. Focusing on two representative meta-problems - Subset Weight Optimization Problem with the c-swap neighborhood and Weighted Circuit with the flip neighborhood - we establish fixed-parameter tractability results related to the number of distinct weights, while ruling out an analogous result when parameterizing by the distance to the nearest optimum via a new type of reduction.
Cite as

Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz. A Parameterized-Complexity Framework for Finding Local Optima. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ITCS.2026.66,
  author =	{Ganian, Robert and Hoang, Hung P. and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Parameterized-Complexity Framework for Finding Local Optima}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{66:1--66:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.66},
  URN =		{urn:nbn:de:0030-drops-253532},
  doi =		{10.4230/LIPIcs.ITCS.2026.66},
  annote =	{Keywords: Local Search, Parameterized Complexity, PLS}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.31
Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis

Authors: Niels Grüttemeier and Klaus Heeger

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider the problem of repairing production schedules in a job-shop setting by reducing pre-planned waiting times. Herein, a schedule of all jobs is given. To compensate unforeseen disturbances, this schedule contains waiting times between the execution of two consecutive tasks of a job. Further, we assume that the schedule temporarily overloads some machines, e.g. due to reduced machine capacities because of worker sickness or (partially) broken machines. We study the problem of removing as few waiting times as possible in order to eliminate the machine overloads. After formalizing this problem, we perform an extensive analysis of its parameterized complexity with respect to several natural parameters, resulting in a detailed picture of the problem’s complexity.
Cite as

Niels Grüttemeier and Klaus Heeger. Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.WADS.2025.31,
  author =	{Gr\"{u}ttemeier, Niels and Heeger, Klaus},
  title =	{{Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.31},
  URN =		{urn:nbn:de:0030-drops-242624},
  doi =		{10.4230/LIPIcs.WADS.2025.31},
  annote =	{Keywords: Job shop, parallel machines, reactive scheduling}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.32
Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems

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

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Parameterized local search combines classic local search heuristics with the paradigm of parameterized algorithmics. While most local search algorithms aim to improve given solutions by performing one single operation on a given solution, the parameterized approach aims to improve a solution by performing k simultaneous operations. Herein, k is a parameter called search radius for which the value can be chosen by a user. One major goal in the field of parameterized local search is to outline the trade-off between the size of k and the running time of the local search step. In this work, we introduce an abstract framework that generalizes natural parameterized local search approaches for a large class of partitioning problems: Given n items that are partitioned into b bins and a target function that evaluates the quality of the current partition, one asks whether it is possible to improve the solution by removing up to k items from their current bins and reassigning them to other bins. Among others, our framework applies for the local search versions of problems like Cluster Editing, Vector Bin Packing, and Nash Social Welfare. Motivated by a real-world application of the problem Vector Bin Packing, we introduce a parameter called number of types τ ≤ n and show that all problems fitting in our framework can be solved in τ^k ⋅ 2^𝒪(k) ⋅ |I|^𝒪(1) time, where |I| denotes the total input size. In case of Cluster Editing, the parameter τ generalizes the well-known parameter neighborhood diversity of the input graph. We complement these algorithms by showing that for all considered problems, an algorithm significantly improving over our algorithm with running time τ^k ⋅ 2^𝒪(k) ⋅ |I|^𝒪(1) would contradict the Exponential Time Hypothesis. Additionally, we show that even on very restricted instances, all considered problems are W[1]-hard when parameterized by the search radius k alone. In case of the local search version of Vector Bin Packing, we provide an even stronger W[1]-hardness result.
Cite as

Niels Grüttemeier, Nils Morawietz, and Frank Sommer. Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.WADS.2025.32,
  author =	{Gr\"{u}ttemeier, Niels and Morawietz, Nils and Sommer, Frank},
  title =	{{Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.32},
  URN =		{urn:nbn:de:0030-drops-242631},
  doi =		{10.4230/LIPIcs.WADS.2025.32},
  annote =	{Keywords: Flip-Neighborhood, Cluster Editing, Vector Bin Packing, Vertex Cover, NP-hard problem, Max c-Cut}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.75
Temporal Graph Realization with Bounded Stretch

Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time steps, where Δ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are "stretched", compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the radius-algorithm) which always guarantees an approximation strictly smaller than Δ, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k.
Cite as

George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Temporal Graph Realization with Bounded Stretch. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2025.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Morawietz, Nils and Spirakis, Paul G.},
  title =	{{Temporal Graph Realization with Bounded Stretch}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{75:1--75:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.75},
  URN =		{urn:nbn:de:0030-drops-241829},
  doi =		{10.4230/LIPIcs.MFCS.2025.75},
  annote =	{Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, stretch}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.14
A Graph-Theoretic Formulation of Exploratory Blockmodeling

Authors: Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present a new simple graph-theoretic formulation of the exploratory blockmodeling problem on undirected and unweighted one-mode networks. Our formulation takes as input the network G and the maximum number t of blocks for the solution model. The task is to find a minimum-size set of edge insertions and deletions that transform the input graph G into a graph G' with at most t neighborhood classes. Herein, a neighborhood class is a maximal set of vertices with the same neighborhood. The neighborhood classes of G' directly give the blocks and block interactions of the computed blockmodel. We analyze the classic and parameterized complexity of the exploratory blockmodeling problem, provide a branch-and-bound algorithm, an ILP formulation and several heuristics. Finally, we compare our exact algorithms to previous ILP-based approaches and show that the new algorithms are faster for t ≥ 4.
Cite as

Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. A Graph-Theoretic Formulation of Exploratory Blockmodeling. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.SEA.2023.14,
  author =	{Bille, Alexander and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Graph-Theoretic Formulation of Exploratory Blockmodeling}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.14},
  URN =		{urn:nbn:de:0030-drops-183648},
  doi =		{10.4230/LIPIcs.SEA.2023.14},
  annote =	{Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks}
}
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.SWAT.2020.26
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs

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

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Given an undirected graph G and integers c and k, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most k edges in G to obtain a graph that has a proper edge coloring with at most c colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed c, a linear-size problem kernel when parameterized by the edge deletion distance of G to a graph with maximum degree c-1. This parameterization measures the distance to instances that, due to Vizing’s famous theorem, are trivial yes-instances. For c≤ 4, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most c and for the list-colored versions of both problems.
Cite as

Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.SWAT.2020.26,
  author =	{Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.26},
  URN =		{urn:nbn:de:0030-drops-122731},
  doi =		{10.4230/LIPIcs.SWAT.2020.26},
  annote =	{Keywords: Graph coloring, social networks, parameterized complexity, kernelization}
}
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}
}
  • Refine by Type
  • 9 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 3 2025
  • 1 2023
  • 3 2020

  • Refine by Author
  • 7 Morawietz, Nils
  • 6 Grüttemeier, Niels
  • 5 Komusiewicz, Christian
  • 3 Sommer, Frank
  • 1 Bille, Alexander
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computing methodologies → Discrete space search
  • 1 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 2 NP-hard problem
  • 2 Parameterized Complexity
  • 1 Branch-and-Bound
  • 1 Cluster Editing
  • 1 Clustering
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact