Temporal path cover problems remain hard with simple graph structures
Tight Hardness for Temporal Path Covers at Vertex-Cover Number Two
Data Structures and Algorithms
Summary
This paper looks at problems involving covering changing networks with paths that follow the order of connections over time. The authors show that these problems are still computationally tough even when the network has a very simple underlying structure. They also find exact boundaries between easy and hard cases based on the network’s vertex cover size. Additionally, they study special cases of star-shaped networks and identify conditions under which solutions can be found efficiently.
What this means in practice
- •For network schedulers: Understand the complexity limits when planning paths over time in networks with simple vertex covers to better design scheduling algorithms.
- •For distributed systems engineers: Recognize which temporal communication patterns in simple network topologies remain hard to optimize for routing or data flow coverage.
A theory result. No direct application yet.
Authors
Alp Par
Abstract
Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TDPC) ask for minimum-cardinality covers of a temporal digraph by temporal paths, with TDPC additionally requiring pairwise temporal disjointness. Cioni et al. proved both problems NP-hard on temporal DAGs whose underlying undirected graph has vertex-cover number three and left the vertex-cover-two case open. We resolve this question affirmatively for both problems. Using polynomial-time reductions from Distinct Numerical Matching with Target Sums, we show that TPC and TDPC are NP-complete already when the underlying undirected graph has vertex-cover number exactly two. For TPC, this yields an exact vertex-cover threshold: polynomial-time solvability at vertex-cover number at most one and NP-completeness at two. For TDPC, we further study the boundary case of temporal oriented stars. A reuse-normalization argument reduces optimum solutions to leaf-unique two-edge merges. If either the incoming or outgoing side is single-label, the optimum remains polynomial-time computable even when the opposite side is multi-label. We also introduce a span parameter for feasible merge realizations and prove that any feasible family of k merges forces a realization of span at least 2k-2. Hence TDPC on temporal oriented stars is in XP parameterized by maximum span, and is polynomial-time solvable for every fixed span bound. The unrestricted multi-label star case remains open.