Minimize number of DFS searches in a graph

Question

I got a weird homework question about graph.

A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed however the helicopter won't know beforehand. Once the the helicopter lands on a house u, they can drive to any neighboring house v if the road (u,v) is not destroyed. The rescue team would only know if a road (u,v) is destroyed or not after they arrive at either u or v. They also don't know the number of safe roads in advance. Design a strategy to minimize the number of helicopter landings, also the plan needs to have less than 2n trips along the safe roads.

My thinking is to do a DFS search on a random unvisted node. After the DFS is done, if there are still unvisited nodes, then do another DFS search from a random unvisited node again. Repeat this until all the nodes are visited. However, I don't know how to prove that this minimize the number of searches. Can anyone help me? Thanks!

Answer 1

Your approach is pretty good.

---

Instead of the word "search", I would prefer "traversal" or "tour".

Here is your strategy/algorithm in slightly different terms.

1. Choose a random unvisited house $h$ to land the helicopter.
2. The rescue team visits all houses connected to $h$ according to a depth-first traversal by driving along safe roads.
3. If there is another unvisited house, which must not be connected to any visited house by a path of safe roads, go back to step 1. Otherwise, stop.

Does the strategy above minimize the number of helicopter landings? Well, for each landing, all houses that can be visited are connected by paths of safe roads. So the number of landings must be at least the number of connected components. The strategy above makes one helicopter landing per one connected component.

---

The next issue is to make sure that a depth-first traversal of a set of $k$ connected houses will make no more than $2k-1$ trips, where a trip means reaching a house from another house by a single safe road.

Here is how we would perform the traversal recursively starting from one random landing at house $h$.

Input: a house $h$.
Output: a series of houses to be passed starting at $h$.
Procedure depth_first_traversal ($h$):
$\quad$output $h$
$\quad$marked $h$ as visited
$\quad$for each unvisited house $i$ connected to $h$ by a safe road:
$\quad$$\quad$call procedure depth_first_traversal ($i$)
$\quad$output $h$

The depth_first_traversal($h$) above will output each node exactly twice, once when it has just been visited and once when all houses connected to it by a safe road have been visited. The number of trips made is one less than the number of the houses passed, i.e., $2k-1$.

Answer 2

Your problem has two clauses:

A) Given a set $V$ of houses, decide on the set of existing edges $\{(u,v)\}$ with a minimal amount of queries (=helicopter landings), when a single query $Q(v)$ reveals all the edges $(v,u)$.

B) Given a graph $G=(V,E)$, find a path that visits all vertices, that traverses at most $2n$ edges.

---

The connectivity problem A has a trivial solution of $O(n)$, which under the model you describe can be easily bounded below by an adversary argument, showing it is also optimal.

Consider the following adversary:

• Choose arbitrary $v_k$ that was not queried before.
• Given query $Q(v_i)$:
  • If $i$ has been asked before, answer accordingly
  • If $i$ is new and $i \neq k$ answer that $v_i$ is only connected to $v_k$
  • If $i$ is new and $i = k$ answer that $v_i$ is connected all previous vertices connected to $v_k$ through previous phase, and to a new vertex $v_j$. Set $v_k \leftarrow v_j$

It is clear any query connects at most $1$ vertex (beside the very first), so regardless of the order of queries an algorithm makes, it must make at least $n-1$ queries to reveal the set of edges, and the connectivity status of the graph.

It follows the naive algorithm of asking all vertices for neighboring edges is also optimal.

---

The traversal problem is simple; find a spanning tree of $G$ (denoted by $T$), after its been revealed by your helicopter. To visits all vertices, do an euler-tour on $T$. Since $T$ has $n-1$ (or less, if it's a spanning forest and $G$ is not connected) edges and an euler tour visits each edge twice, you visits all vertices at the maximal cost of $2n-2$ edges.