NMNils Morawietz

Nils Morawietz

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Parameterized Local Search for Max c-Cut

    by Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz

    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$$ 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$$ c ≥ 2 , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ f ( k ) · n 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)$$ O ( ( 3 e Δ ) k · c · k 3 · Δ · 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.

  • Towards Settling the Complexity of the Lettericity Problem

    by Mario Grobler, Nils Morawietz, Silas Cato Sacher

  • Open Access

    Temporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions

    by Anton Herrmann, Christian Komusiewicz, Nils Morawietz, Frank Sommer

  • Open Access

    Temporal graph realization with bounded stretch

    by George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis

  • Open Access

    Graph clustering problems under the lens of parameterized local search

    by Jaroslav Garvardt, Nils Morawietz, André Nichterlein, Mathias Weller

  • Open Access

    The Parameter Report: An Orientation Guide for Data-Driven Parameterization

    by Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus

    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

    Realizing Temporal Transportation Trees

    by George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis


  • Open Access

    Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard

    by Christian Komusiewicz, Nils Morawietz

    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

    Can Local Optimality Be Used for Efficient Data Reduction?

    by Christian Komusiewicz, Nils Morawietz

    An independent set S in a graph G is k-swap-optimal if there is no independent set $$S'$$ S ′ such that $$\varvec{|S'|>|S|}$$ | S ′ | > | S | and $$\varvec{|(S'\setminus S)\cup (S\setminus S')|\le k}$$ | ( S ′ \ S ) ∪ ( S \ S ′ ) | ≤ 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}}$$ Σ 2 P -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)}}$$ f ( Δ + k ) · n O ( 1 ) time whether it is in some k-optimal path.