Nils Morawietz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Nils Morawietz has a total of 8 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
3 shared publications - Niels Grüttemeier
Fraunhofer IOSB-INA Lemgo Germany
3 shared publications Niels Grüttemeier
2 shared publications- Petra Wolf
Universität Trier
2 shared publications Christian Komusiewicz
1 shared publication
Latest Publications
- 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- Open Access
- 22 September 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 66 (5) , 1019-1045
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.
- 22 September 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 66 (5) , 1019-1045
Open AccessRefined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.
- 20 September 2021
- Published by Springer Nature
- p. 143-155
Preventing Small $\mathbf {(s,t)}$-Cuts by Protecting Edges- 20 September 2021
- Published by Springer Nature
- p. 143-155
Preventing Small $\mathbf {(s,t)}$-Cuts by Protecting Edges- Open Access
A Timecop's Chase Around the Table
We consider the cops and robber 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 the infinite TVG. We proof 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 and Robber on general edge periodic graphs to PSPACE-membership.Open AccessA Timecop's Chase Around the Table
We consider the cops and robber 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 the infinite TVG. We proof 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 and Robber on general edge periodic graphs to PSPACE-membership. - 4 May 2021
- Published by Springer Nature
- p. 354-366
Can Local Optimality Be Used for Efficient Data Reduction?
- 4 May 2021
- Published by Springer Nature
- p. 354-366
Can Local Optimality Be Used for Efficient Data Reduction?
- Open Access
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
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\le 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.Open AccessMaximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
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\le 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. - 17 January 2020
- Published by Springer Nature
- p. 248-259
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
- 17 January 2020
- Published by Springer Nature
- p. 248-259
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs