Research map / Graph learning / Knowledge and temporal graphs
How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the exact edge-cover problem in temporal graphs, where each temporal edge must be covered exactly once by k temporal journeys (paths, trails, or walks), giving complexity dichotomies over strictness, directedness, and fixed terminals.
Problem
Minimizing the number of temporal journeys needed to exactly cover all temporal edges of a temporal graph, a model for resource-efficient transportation planning.
Approach
Formulates a temporal exact edge-cover problem where every temporal edge is covered exactly once by k journeys of a given type (path, trail, walk), and resolves its complexity across four dimensions (journey type, strictness, directedness, fixed terminals) via NP-hardness reductions, SAT/XOR-SAT reductions for k=2, and dynamic programs for walks.
Key results
- Exact edge-cover by two journeys is polynomial (via 2-SAT / XOR-SAT) for most variants, but NP-complete for non-strict trails on directed and undirected graphs.
- For k>=3, strict and non-strict path exact edge-cover is NP-complete on directed and undirected temporal graphs, and no polynomial alpha-approximation exists for any alpha>1 unless P=NP.
- For walks, the problem is polynomial for any constant k (O(n^O(k))) and strict walks on directed graphs are solvable in linear time O(|E|) given the edgestream.
Surprising findings
- Walks, unlike paths and trails, remain polynomial for any constant k, contrasting with intractability for paths and trails at k>=3.
Limitations
- Fixed-terminal variants and some walk cases (non-strict walks on undirected graphs with fixed terminals, W[2]-hardness for non-strict directed walks) are only partially resolved.
- Hardness results are theoretical; no empirical evaluation on real transportation networks.
Experimental setup
Builds on: temporal exploration edge-disjoint path cover NAE-SAT XOR-SAT
Closest papers by meaning
- Approximating Optimal Labelings for Temporal Connectivity (AAAI 2025 · similarity 0.87)
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.84)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.83)
- Speedup Techniques for Switchable Temporal Plan Graph Optimization (AAAI 2025 · similarity 0.83)
- Semantic Routing via Autoregressive Modeling (NeurIPS 2024 · similarity 0.82)
- Towards Dynamic Spatial-Temporal Graph Learning: A Decoupled Perspective (AAAI 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.