Let $G$ be a DAG. We know that some nodes in $G$ are bad, while the others are good; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have a unique minimal element in $G$ which we'd like to find querying as few nodes as possible with queries of the type Are you good or bad?.This problem is solved in Git, the popular version control system, by the command git-bisect, which helps a programmer find the first commit in which a bug was introduced.At the start, the algorithm implemented by Git assumes to know a single bad commit and one or more good commits. At each step of its execution, the algorithm finds a commit using the following steps (taken from here):Keep only the commits that:a) are an ancestor of the bad commit (including the bad commit itself), andb) are not an ancestor of a good commit (excluding the good commits).Starting from the good ends of the resulting graph, associate to eachcommit the number of ancestors it has plus one.Associate to each commit $\min(X, N-X)$, where $X$ is the value associated to the commit in step 2, and $N$ is the total number of commits in the graph (after it was reduced in step 1).The best bisection point is the commit with the highest associatednumber.This algorithm is essentially finding the commit that achieves the worst best case: in fact, $\min(X,N-X)$ is the number of nodes in the DAG at the next iteration in the best case, thus $\max\min(X,N-X)$ is the worst best case.I'm wondering:Does it make any difference if we select the best worst case, that is, the node that achieves $\min\max(X,N-X)$?Is this algorithm worst-case optimal?EDIT: I've noticed that this problem has a $\Omega(N)$ bound. Consider the DAG formed by a single node $b$ with $N-1$ parents called $g_1,\dots,g_{N-1}$. If we know that $b$ is bad then we have check each of the parents to see if they are the minimal bad node.EDIT 2: The previous is actually a $\Omega(w)$ bound, where $w$ is the width of the poset. An alternative algorithm for this problem is given in this answer on cstheory.stackexchange that uses $O(w\log{n})$ queries.
Is the algorithm implemented by git bisect optimal?
algorithms;graphs