How would I show the parenthesis theorem doesn't work for Breadth First Search?

Question

I'm trying to think of how exactly to show the parenthesis theorem does not work for breadth first search.

For depth first search, it works exactly like nested parenthesis because everything falls under these three properties:

1. The intervals [d[u], f[u]] and [d[v], f[v]] are entirely disjoint and neither u nor v is a descendant of the other in the depth-first forest.

2. The interval [d[u], f[u]] is contained within the interval [d[v], f[v]], and u is a descendant of v in a depth-first tree.

3. The interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]], and v is a descendant of u in a depth-first tree.

How would I show it doesn't work for breadth first search?

Answer 1

In general, to disprove a theorem, you need find only one counterexample. In your case, that would be a single breadth-first traversal (of some graph) that doesn't satisfy the parenthesis theorem.

But the problem you're facing is that the parenthesis theorem isn't really a general statement about graph traversals that could be true or false of a given traversal and happens to be true of all depth-first traversals; rather, the parenthesis theorem is a specific statement about depth-first traversals that is true of all of them. Phrases like "the interval [d[u], f[u]]" and "the depth-first forest" are clear references to depth-first traversals; they don't have obvious/unique definitions that you can apply to breadth-first traversals.

So what you need to do is:

1. Decide what the parenthesis theorem would mean for a breadth-first traversal. There are a few ways you might go about that, such as:
   • come up with appropriate "breadth-first" definitions for all of the terms used in the theorem.
   • rephrase the parenthesis theorem in a more general way.
   • define a "breadth-first parenthesis theorem" that's analogous to the existing "depth-first parenthesis theorem" but with all terms replaced by appropriate analogues.
2. Find a breadth-first traversal (of some small graph) that doesn't satisfy the theorem under those definitions.