Nils Morawietz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Nils Morawietz has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Christian Komusiewicz
Institute of Computer Science, Friedrich Schiller University Jena, Jena, Germany
4 shared publications - Frank Sommer
Institute of Logic and Computation TU Wien Austria
2 shared publications André Nichterlein
1 shared publication- Anton Herrmann1 shared publication
Christian Komusiewicz
1 shared publicationGeorge B. Mertzios
1 shared publication
Latest Publications
- Open Access
- 17 September 2026
- Published by Springer Nature in Annals of Operations Research
- Vol. 365 (2-3) , 523-563
Parameterized Local Search for Max c-Cut
In the NP-hard Max c -Cut problem, one is given an undirected edge-weighted graph G and aims to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $$c=2$$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max c -Cut where we are also given a vertex coloring and an integer k and the task is to find a better coloring that changes the color of at most k vertices, if such a coloring exists; otherwise, the given coloring is k -optimal. We show that, for all $$c\ge 2$$ , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time $$\mathcal {O}((3e\Delta )^k\cdot c\cdot k^3\cdot \Delta \cdot n)$$ , where $$\Delta $$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max c -Cut . We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances.- 17 September 2026
- Published by Springer Nature in Annals of Operations Research
- Vol. 365 (2-3) , 523-563
Open AccessParameterized Local Search for Max c-Cut
In the NP-hard Max c -Cut problem, one is given an undirected edge-weighted graph G and aims to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $$c=2$$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max c -Cut where we are also given a vertex coloring and an integer k and the task is to find a better coloring that changes the color of at most k vertices, if such a coloring exists; otherwise, the given coloring is k -optimal. We show that, for all $$c\ge 2$$ , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time $$\mathcal {O}((3e\Delta )^k\cdot c\cdot k^3\cdot \Delta \cdot n)$$ , where $$\Delta $$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max c -Cut . We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances. - 20 July 2026
- Published by Springer Nature
- p. 304-319
Towards Settling the Complexity of the Lettericity Problem
- 20 July 2026
- Published by Springer Nature
- p. 304-319
Towards Settling the Complexity of the Lettericity Problem
- Open Access
- 10 July 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1084
Temporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions
- 10 July 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1084
Open AccessTemporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions
- Open Access
- 5 May 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 160
Temporal graph realization with bounded stretch
- 5 May 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 160
Open AccessTemporal graph realization with bounded stretch
- Open Access
- 26 February 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 159
Graph clustering problems under the lens of parameterized local search
- 26 February 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 159
Open AccessGraph clustering problems under the lens of parameterized local search
- Open Access
- 17 January 2026
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 30 (1) , 385-419
The Parameter Report: An Orientation Guide for Data-Driven Parameterization
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is unclear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. This question cannot be answered from purely theoretical considerations and any answer requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our results may help assess the significance of FPT-running time bounds on the solvability of real-world instances. For example, the vertex cover number $vc$ of $n$-vertex graphs is often only slightly below $n/2$. Thus, a running time bound of $O(2^{vc})$ is only slightly better than a running time bound of $O(1.4^{n})$. In contrast, the treewidth $tw$ is almost always below $n/3$ and often close to $n/9$, making a running time of $O(2^{tw})$ much more practical on real-world instances.We make our implementation and full experimental data openly available. In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity.- 17 January 2026
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 30 (1) , 385-419
Open AccessThe Parameter Report: An Orientation Guide for Data-Driven Parameterization
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is unclear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. This question cannot be answered from purely theoretical considerations and any answer requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our results may help assess the significance of FPT-running time bounds on the solvability of real-world instances. For example, the vertex cover number $vc$ of $n$-vertex graphs is often only slightly below $n/2$. Thus, a running time bound of $O(2^{vc})$ is only slightly better than a running time bound of $O(1.4^{n})$. In contrast, the treewidth $tw$ is almost always below $n/3$ and often close to $n/9$, making a running time of $O(2^{tw})$ much more practical on real-world instances.We make our implementation and full experimental data openly available. In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity. - Top Cited Papers
- 2 January 2026
- Published by Springer Nature
- p. 390-404
Realizing Temporal Transportation Trees
- 2 January 2026
- Published by Springer Nature
- p. 390-404
Top Cited PapersRealizing Temporal Transportation Trees
- Open Access
- 13 June 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1051
Parameterized algorithms for multi-label periodic temporal graph realization
- 13 June 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1051
Open AccessParameterized algorithms for multi-label periodic temporal graph realization
- Open Access
- 15 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (1) , 1-31
Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Local search problems consist of a set of feasible solutions, an objective function, and a neighborhood relation which assigns to each feasible solution a set of neighbors. A solution S is called locally optimal if none of its neighbors has a better objective value than S . For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and finding a better one if this is not the case can be done in polynomial time. We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the collection of vertex sets which can be obtained from S by exchanging at most three vertices. On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. Using the PLS-completeness for independent sets with the 3-swap-neighborhood, we also show PLS-completeness for a large class of maximum-weight subgraph problems. On the positive side, we show that locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except (a) the swaps that remove two vertices from the current solution and add one vertex to the solution or (b) the swaps that remove one vertex from the current solution and add two vertices to the solution. This result is shown via general algorithms for subset-weight optimization problems with a restricted k -swap neighborhood.
- 15 February 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (1) , 1-31
Open AccessFinding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Local search problems consist of a set of feasible solutions, an objective function, and a neighborhood relation which assigns to each feasible solution a set of neighbors. A solution S is called locally optimal if none of its neighbors has a better objective value than S . For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and finding a better one if this is not the case can be done in polynomial time. We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the collection of vertex sets which can be obtained from S by exchanging at most three vertices. On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. Using the PLS-completeness for independent sets with the 3-swap-neighborhood, we also show PLS-completeness for a large class of maximum-weight subgraph problems. On the positive side, we show that locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except (a) the swaps that remove two vertices from the current solution and add one vertex to the solution or (b) the swaps that remove one vertex from the current solution and add two vertices to the solution. This result is shown via general algorithms for subset-weight optimization problems with a restricted k -swap neighborhood.
- Open Access
- 23 January 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (1) , 1-34
Can Local Optimality Be Used for Efficient Data Reduction?
An independent set S in a graph G is k-swap-optimal if there is no independent set $$S'$$ such that $$\varvec{|S'|>|S|}$$ and $$\varvec{|(S'\setminus S)\cup (S\setminus S')|\le k}$$ . Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap-optimal independent set or in all k-swap-optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are $$\varvec{\Sigma ^{\text {P}}_{2}}$$ -hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in $$\varvec{f(\Delta +k)\cdot n^{\mathcal {O}(1)}}$$ time whether it is in some k-optimal path.- 23 January 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (1) , 1-34
Open AccessCan Local Optimality Be Used for Efficient Data Reduction?
An independent set S in a graph G is k-swap-optimal if there is no independent set $$S'$$ such that $$\varvec{|S'|>|S|}$$ and $$\varvec{|(S'\setminus S)\cup (S\setminus S')|\le k}$$ . Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap-optimal independent set or in all k-swap-optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are $$\varvec{\Sigma ^{\text {P}}_{2}}$$ -hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in $$\varvec{f(\Delta +k)\cdot n^{\mathcal {O}(1)}}$$ time whether it is in some k-optimal path.