arXiv preprint ·
Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time step wait or move along an edge of the current snapshot, and the temporal graph is explored once the agent has visited every vertex. We consider always-connected temporal graphs, in which every snapshot is connected, and ask how long exploration can be forced to take when the underlying graph, the union of all snapshots, has maximum degree at most~$Δ$. Two lower bounds were known in this setting, $Ω(Δn)$ and $Ω(n\log n)$, realised by different constructions. We establish a stronger lower bound, answering a question of Bastide, Groenland, Michel and Rambaud. Specifically, for every $n$ and $Δ$ with $Δ_0\leΔ\le n-1$ we construct an always-connected temporal graph on $n$ vertices with underlying maximum degree at most~$Δ$ that cannot be explored in fewer than $γ\,Δn\,(1+\log(n/Δ))$ time steps from any start vertex, where $γ>0$ and $Δ_0$ are absolute constants. The construction is deterministic, and every snapshot is a spanning tree with exactly one vertex of degree greater than three. Time is divided into phases. In each phase, a rotating-cycle gadget prevents the agent from reaching more than half of the trees attached to it. Between phases, we reassign target vertices among these trees using walks on a constant-degree expander, and a Gray code order of the targets keeps the underlying degree bounded. The reassignment guarantees that, for any walk of the agent, some target remains unvisited throughout all phases.
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
Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
On the complexity of the single-move labeled token routing problem
On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs
Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
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.