Author name cluster

Nils Morawietz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

TCS Journal 2025 Journal Article

Parameterized algorithms for multi-label periodic temporal graph realization

Thomas Erlebach
Nils Morawietz
Petra Wolf

In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n × n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D. We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to ℓ times in each period, for some given integer ℓ. For the resulting problem Multi-Label Periodic TGR, we show that it is fixed-parameter tractable for parameter n and for parameter vc + Δ, where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu + d max, where nu is the number of non-universal vertices of the underlying graph and d max is the largest entry of D. Furthermore, we show that the problem is NP-hard for each ℓ ≥ 5, even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if ℓ = 1.

Details DOI

MFCS Conference 2025 Conference Paper

Temporal Graph Realization with Bounded Stretch

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

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.

Details

MFCS Conference 2024 Conference Paper

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Arnaud Casteigts
Nils Morawietz
Petra Wolf 0002

A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph 𝒢 is from being transitive, namely, vertex-deletion distance to transitivity and arc-modification distance to transitivity, both being applied to the reachability graph of 𝒢. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.

Details

MFCS Conference 2024 Conference Paper

On the Complexity of Community-Aware Network Sparsification

Emanuel Herrendorf
Christian Komusiewicz
Nils Morawietz
Frank Sommer

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.

Details

MFCS Conference 2023 Conference Paper

On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric

Jana Holznigenkemper
Christian Komusiewicz
Nils Morawietz
Bernhard Seeger

We initiate a study of the complexity of MSM-Median, the problem of computing a median of a set of k real-valued time series under the move-split-merge distance. This distance measure is based on three operations: moves, which may shift a data point in a time series; splits, which replace one data point in a time series by two consecutive data points of the same value; and merges, which replace two consecutive data points of equal value by a single data point of the same value. The cost of a move operation is the difference of the data point value before and after the operation, the cost of split and merge operations is defined via a given constant c. Our main results are as follows. First, we show that MSM-Median is NP-hard and W[1]-hard with respect to k for time series with at most three distinct values. Under the Exponential Time Hypothesis (ETH) our reduction implies that a previous dynamic programming algorithm with running time |I|^𝒪(k) [Holznigenkemper et al. , Data Min. Knowl. Discov. '23] is essentially optimal. Here, |I| denotes the total input size. Second, we show that MSM-Median can be solved in 2^𝒪(d/c)⋅|I|^𝒪(1) time where d is the total distance of the median to the input time series.

Details

IJCAI Conference 2023 Conference Paper

Parameterized Local Search for Max c-Cut

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 wants 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 additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ 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 state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.

PDF Details DOI

TCS Journal 2022 Journal Article

Colored cut games

Nils Morawietz
Niels Grüttemeier
Christian Komusiewicz
Frank Sommer

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 colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. The attacker wants to achieve a colored ( s, t ) -cut and the defender wants to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete even on subcubic graphs. We then show that, even on subcubic graphs, colored cut games with i 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 maximum degree at most 2. Next, 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. For κ 1, which is the vertex cover number vc of the input graph, the kernel has size O ( vc 2 k 2 ). Moreover, we introduce an algorithm solving the most basic colored cut game, Colored ( s, t ) -Cut, in 2 vc + k n O ( 1 ) time.

Details DOI

MFCS Conference 2022 Conference Paper

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

Christian Komusiewicz
Nils Morawietz

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 replacing it by 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 set of vertex sets which can be obtained from S by exchanging at most three vertices. We prove the following dichotomy: On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. On the positive side, 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.

Details

MFCS Conference 2021 Conference Paper

A Timecop's Chase Around the Table

Nils Morawietz
Petra Wolf 0002

We consider the cops and robbers game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i. e. , for each edge, a binary string s_e determines in which time step the edge is present, namely the edge e is present in time step t if and only if the string s_e contains a 1 at position t mod |s_e|. This periodicity allows for a compact representation of an infinite TVG. We prove that even for very simple underlying graphs, i. e. , directed and undirected cycles the problem whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Our second main result are matching lower bounds for the ratio between the length of the underlying cycle and the least common multiple (lcm) of the lengths of binary strings describing edge-periodicies over which the graph is robber-winning. Our third main result improves the previously known EXPTIME upper bound for Periodic Cop & Robber on general edge periodic graphs to PSPACE-membership.

Details

AAAI Conference 2021 Conference Paper

Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings

Niels Grüttemeier
Christian Komusiewicz
Nils Morawietz

In Bayesian Network Structure Learning (BNSL), we are given a variable set and parent scores for each variable and aim to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are computationally hard, and, thus, in practice heuristics such as local search are used. In a typical local search algorithm, we are given some BNSL solution and ask whether there is a better solution within some pre-defined neighborhood of the solution. We study ordering-based local search, where a solution is described via a topological ordering of the variables. We show that given such a topological ordering, we can compute an optimal DAG whose ordering is within inversion distance r in subexponential FPT time; the parameter r allows to balance between solution quality and running time of the local search algorithm. This running time bound can be achieved for BNSL without any structural constraints and for all structural constraints that can be expressed via a sum of weights that are associated with each parent set. We show that for other modification operations on the variable orderings, algorithms with an FPT time for r are unlikely. We also outline the limits of ordering-based local search by showing that it cannot be used for common structural constraints on the moralized graph of the network.

PDF Details

IJCAI Conference 2021 Conference Paper

On the Parameterized Complexity of Polytree Learning

Niels Grüttemeier
Christian Komusiewicz
Nils Morawietz

A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of Polytree Learning. We show that Polytree Learning can be solved in single-exponential FPT time for the number of variables. Moreover, we consider the influence of d, the number of variables that might receive a nonempty parent set in the final DAG on the complexity of Polytree Learning. We show that Polytree Learning is presumably not fixed-parameter tractable for d, unlike Bayesian network learning which is fixed-parameter tractable for d. Finally, we show that if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.

PDF Details DOI

MFCS Conference 2020 Conference Paper

A Timecop's Work Is Harder Than You Think

Nils Morawietz
Carolin Rehs
Mathias Weller

We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph.

Details