Author name cluster

Philipp Zschoche

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.

7 papers

2 author rows

IJCAI Conference 2022 Conference Paper

Disentangling the Computational Complexity of Network Untangling

Vincent Froese
Pascal Kunz
Philipp Zschoche

We study the recently introduced network untangling problem, a variant of Vertex Cover on temporal graphs---graphs whose edge set changes over discrete time steps. There are two versions of this problem. The goal is to select at most k time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.

PDF Details DOI

JAAMAS Journal 2022 Journal Article

Interference-free walks in time: temporally disjoint paths

Nina Klobas
George B. Mertzios
Philipp Zschoche

Abstract We investigate the computational complexity of finding temporally disjoint paths and walks in temporal graphs. There, the edge set changes over discrete time steps. Temporal paths and walks use edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never visit the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. At one extreme, we show that on general graphs the problem is computationally hard. The path version is NP-hard even if we want to find only two temporally disjoint paths. The walk version is W-hard (Klobas in IJCAI 4090–4096, 2021) when parameterized by the number of walks. However, it is polynomial-time solvable for any constant number of walks. At the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.

Details DOI

IJCAI Conference 2021 Conference Paper

Interference-free Walks in Time: Temporally Disjoint Paths

Nina Klobas
George B. Mertzios
Hendrik Molter
Rolf Niedermeier
Philipp Zschoche

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.

PDF Details DOI

MFCS Conference 2021 Conference Paper

Temporal Reachability Minimization: Delaying vs. Deleting

Hendrik Molter
Malte Renken
Philipp Zschoche

We study spreading processes in temporal graphs, i. e. , graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.

Details

MFCS Conference 2021 Conference Paper

The Complexity of Transitively Orienting Temporal Graphs

George B. Mertzios
Hendrik Molter
Malte Renken
Paul G. Spirakis
Philipp Zschoche

In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i. e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u, v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

Details

TCS Journal 2020 Journal Article

Temporal graph classes: A view through temporal separators

Till Fluschnik
Hendrik Molter
Rolf Niedermeier
Malte Renken
Philipp Zschoche

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal ( s, z ) -Separation problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.

Details DOI

MFCS Conference 2018 Conference Paper

The Complexity of Finding Small Separators in Temporal Graphs

Philipp Zschoche
Till Fluschnik
Hendrik Molter
Rolf Niedermeier

Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.

Details