Research map / Graph learning / Graph algorithms and clustering
Approximating Optimal Labelings for Temporal Connectivity
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 Minimum Aged Labeling (MAL) problem for temporal graphs, proving new approximation hardness bounds (log n for a=2 and 2^{log^{1-ε} n} for a≥3) and giving approximation algorithms that depend on the relation between the age bound a and the graph diameter, via a connection to Diameter Constrained Spanning Subgraph (DCSS).
Problem
Minimum Aged Labeling: assign the fewest time-labels to edges of an undirected graph so that all vertex pairs are temporally connected within maximum age a; also the related DCSS problem.
Approach
Shows approximation hardness for undirected MAL via reductions from Set Cover and Min-Rep, relates MAL to DCSS with a factor-b transfer, and gives algorithms whose ratios depend on a versus diameter D_G and radius R_G (including sublinear bounds for a >= 3/2 D_G).
Key results
- MAL on undirected graphs cannot be approximated within (epsilon log n) for a=2 unless P=NP, and within 2^{log^{1-ε} n} for a>=3 unless NP ⊆ DTIME(2^{polylog n}).
- If a >= 2R_G, a polynomial-time solution uses at most 2 labels more than optimum; if a >= 2D_G+2, MAL is solvable optimally in polynomial time.
- For a >= ceil(3/2 D_G), MAL admits an O(sqrt(n log n))-approximation; for a >= ceil(5/3 D_G), an O(cuberoot(D_G n log^2 n))-approximation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Raise the age bound to a ≥ ⌈3/2 · D_G⌉ and use the proposed direct MAL algorithm | MAL · MAL, a ≥ ⌈3/2 · D_G⌉ | approximation ratio: O(√(n log n)) | Helped |
| Raise the age bound to a ≥ ⌈5/3 · D_G⌉ and use the proposed direct MAL algorithm | MAL · MAL, a ≥ ⌈5/3 · D_G⌉ | approximation ratio: O(∛(D_G n log² n)) | Helped |
| Increase the age allowance to a ≥ 2R_G | MAL · MAL, a ≥ 2R_G | additive labels above optimum: |λ| ≤ |λ*| + 2 | Helped |
| Increase the age allowance from a ≥ 2R_G to a ≥ 2R_G + 1 | MAL shortest-path-tree labeling · MAL, a ≥ 2R_G + 1 | additive labels above optimum: |λ| ≤ |λ*| + 1 | Helped |
| Increase the age allowance to a ≥ 2D_G + 2 | MAL · MAL, a ≥ 2D_G + 2 | optimality gap: |λ| = |λ*| | Helped |
| Use the DCSS-based approach when a = 2 | MAL · MAL, a = 2 | approximation ratio: O(log(n)) | Helped |
| Use the DCSS-based approach for any a ≥ D_G | MAL · MAL, a ≥ D_G | approximation ratio: O(D_G·n^{3/5+ε}) | Helped |
| Increase the age allowance to a ≥ D_G + 2 | MAL via DCSS · MAL, a ≥ D_G + 2 | approximation ratio: O(D_G·n^{1/2}) | Helped |
| Increase the age allowance to a ≥ D_G + 4 | MAL via DCSS · MAL, a ≥ D_G + 4 | approximation ratio: O(D_G·n^{2/5}) | Helped |
| Increase the age allowance to a ≥ D_G + 6 | MAL via DCSS · MAL, a ≥ D_G + 6 | approximation ratio: O(D_G·n^{1/3}) | Helped |
Limitations
- Hardness results require a = D_G, leaving D_G < a < 2R_G open.
- Gap of factor D_G between MAL and DCSS approximation transfers for some algorithms.
- Text is truncated; some proofs and the full algorithm for the main theorem are not visible.
Experimental setup
Metrics: approximation ratio
Baselines: trivial O(n)-approximation via shortest path trees
Builds on: Minimum Aged Labeling Set Cover hardness Min-Rep hardness Diameter Constrained Spanning Subgraph additive spanners
Closest papers by meaning
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.87)
- How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs (AAAI 2025 · similarity 0.87)
- Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs (NeurIPS 2024 · similarity 0.85)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.85)
- Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · similarity 0.85)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.84)
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.