8
$\begingroup$

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):

  1. Keep only the commits that:

    a) are an ancestor of the bad commit (including the bad commit itself), and

    b) are not an ancestor of a good commit (excluding the good commits).

  2. Starting from the good ends of the resulting graph, associate to each commit the number of ancestors it has plus one.

  3. 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).

  4. The best bisection point is the commit with the highest associated number.

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.

$\endgroup$
  • 1
    $\begingroup$ We can't answer whether it is optimal without defining what we mean by optimal. In particular, are we talking about worst-case complexity? Average-case complexity? What is the typical workload? (What does the typical graph look like? what is the distribution on graphs?) Those questions are very important in practice, but may not have a clean or simple analytical answer. $\endgroup$ – D.W. Mar 11 '14 at 0:20
  • $\begingroup$ I'm mostly interested in worst-case complexity. I tried constructing instances in which the greedy algorithm takes too many wrong choices, but was unable to do so. Of course, the typical git graph has lots of structure (I'd expect a long-ish chain in which most commits lie: the master branch), but it's probably too hard to characterize. $\endgroup$ – Jacopo Notarstefano Mar 11 '14 at 7:34
  • 1
    $\begingroup$ I don't really understand what you are asking, but the following inequality may be useful: For any function of two variables $f$, it is always the case that $\max_x \min_y f(x,y) \le \min_x \max_y f(x,y)$. See for example, math.stackexchange.com/a/186722/3060 $\endgroup$ – Nick Alger Jul 7 '14 at 23:28
5
$\begingroup$

Here's some intuition for what $X$ and $N$ are doing. Focus on a particular commit $c$. Suppose we test $c$ and classify it as either "good" or "bad". Until we test it, we don't know whether it is good or bad, but we can predict in advance how much smaller the graph will get in each of those two cases. In particular, $X$ is the number of commits that would be trimmed away if commit $c$ turns out to be good, and $N-X$ is the number of commits that would be trimmed away if commit $c$ turns out to be bad.

Therefore, the value $\min(X,N-X)$ is a lower bound on the number of commits we'll be able to trim away in the next step, no matter how the test turns out. The idea of the Git algorithm is to maximize of this metric. In other words, Git picks a threshold $t$ that is as large as possible, and a commit $c$ to test next, such that Git can be sure that it'll be able to trim away at least $t$ commits in the next step.

If we have no information about whether each commit is likely to turn out good or bad, so it's equally likely that it's good or bad, then this looks like a locally optimal choice. Thus, the Git algorithm is a greedy algorithm.

Is the Git algorithm globally optimal? That will depend upon the definition of "optimal", and (probably) on the distribution of DAGs one encounters in practice. Probably there is no simple characterization of the probability distribution on DAGs one encounters in practice, so I'd expect it is probably going to be difficult to find an optimality result for this problem.

$\endgroup$
  • 2
    $\begingroup$ While this is an interesting explanation, this is not an answer to my question, so I can't accept it. $\endgroup$ – Jacopo Notarstefano Mar 17 '14 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.