The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
[CF23] NairenCaoandJeremyTFineman
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3verdicts
UNVERDICTED 3representative citing papers
Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.
A greedy algorithm matches recent optimal size/hopbound tradeoffs for shortcut sets and receives a new existential optimality proof for matching hopsets up to logarithmic factors.
citing papers explorer
-
Revisiting Diameter in Directed Graphs
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
-
Maximizing Reachability via Shifting of Temporal Paths
Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.
-
Greedy Algorithms for Shortcut Sets and Hopsets
A greedy algorithm matches recent optimal size/hopbound tradeoffs for shortcut sets and receives a new existential optimality proof for matching hopsets up to logarithmic factors.