Treasure hunt: Treasure hunt with advice

Treasure hunt

One agent must find a static treasure at an unknown node; the cost should depend on how far the treasure is, not on the size of the graph.

Problem statement and measuresexpand

A single deterministic agent starts at a node \(s\) of an unknown connected graph whose edges carry ports (at each node, local numbers of the edges at that node); a treasure sits at an unknown node \(v^*\) at distance \(d\) from \(s\). The agent must reach \(v^*\) (it recognises the treasure when it arrives). Cost is the number of moves (edge traversals) until the treasure is found, measured against \(d\), against \(e(d)\) (the number of edges with an endpoint at distance less than \(d\) from \(s\)) or against a path weight defined per paper. Help counts any external help the agent receives: bits of advice from an oracle that knows the instance, or pebbles (objects left on nodes) placed by it. Unless a variant says otherwise the agent knows nothing about the graph, \(d\) or \(v^*\).

Measures: Cost, edge traversals until the treasure is reached; Help, bits of advice, or pebbles placed in advance by an oracle.

no assumptions›+ static graph, + undirected›+ finite graph›+ advice

Treasure hunt with advice

verified

Cost: tightHelp: near-optimal

How many bits of advice buy a given cost \(C\): about \(d\log(m/C)\).

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Graph sizefinite+External helpadvice: bits from an oracle that knows the instance

Not assumed

Node identifiersanonymous nodesTopologyarbitrary connected graph

Formal definitions of this setting

Graph dynamics: static graph: \(G_t=G\) for all \(t\): the edge set never changes.
Edge direction: undirected: \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Graph size: finite graph: \(G\) has finitely many nodes.
Node identifiers: anonymous nodes: Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
External help: advice: An oracle that knows the whole instance gives the agent a binary string before it starts; its length (in bits) is the measure.
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

What is known

Cost · edge traversals until the treasure is reached

tight

Cost \(C\) is the measure to minimise.

lower boundnone known

introductory—

current best

\(C\)

Miller & Pelc 2015

Help · bits of advice, or pebbles placed in advance by an oracle

near-optimal

A \(\log d\) inside the first term on arbitrary graphs.

lower bound

\(\Omega(d\log(m/C))\) Miller & Pelc 2015

bottleneckinformation

holds when

to achieve cost \(C\)
\(d\) = distance to the treasure, \(m\) = number of edges

introductory—

current best

\(O(d\log(d\cdot m/C)+\log\log m)\)

Miller & Pelc 2015

Results, in order of publication

Miller & Pelc 2015 current best

Cost \(C\)Help \(O(d\log(d\cdot m/C)+\log\log m)\)

Introductory and current best; on trees \(O(d\log(m/C)+\log\log m)\), nearly tight.

Open questions

None recorded for this variant.

Notes

The same paper gives the analogous trade-off for rendezvous.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

Anonymous finite graphs

Cost \(O(n^{\theta(1+1/a)})\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.