arXiv preprint ·
Tight Hardness for Temporal Path Covers at Vertex-Cover Number Two
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Prefix Sharing Is a Sorting Problem
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.