[darcs-devel] conflict resolution: an efficient algorithm

Benjamin Franksen ben.franksen at online.de
Thu May 17 13:46:08 UTC 2018


The algorithm I presented is incorrect and the conclusions drawn
therefore obsolete. The problem is that C0(s,q) is /not/ a superset of
all solutions that don't contain s because neither "conflicts with" nor
"does not conflict with" are transitive relations. Thus solving the
subproblem for C0(s,q) is not enough to determine all maximal
non-conflicting subsets that do not contain s.

In fact, the problem of finding maximal non-conflicting subsets is
equivalent to a well-known problem in graph theory, namely that of
finding the maximal cliques of a simple graph. The vertices of the graph
are the elements of C(q) and an edge means "does not conflict with".

This problem is NP-complete in general (according to wikipedia).

There are a number of graph classes for which it is solvable in
polynomial time and I think our concrete problem should be in one of
those classes. A good candidate are comparability graphs since our main
target are hunk patches: a set of transitively conflicting hunks must be
in the same file and thus all pairs among them that are not in conflict
can be strictly ordered. Another way to see this is that the complement
graph (where an edge means "conflict") is an interval graph, where the
interval is the the set of lines modified by the hunk.

Wikipedia tells me that there is a quadratic time algorithm for finding
the maximal cliques of a comparability graph but unfortunately the
article is behind a paywall. Here is the citation: Even, S.; Pnueli, A.;
Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal
of the ACM, 19 (3): 400–410). If someone has access to a copy...

BTW, given some strict order between non-conflicting pairs of patches
(which is the definiton of a comparability graph) it seems that maximal
cliques must actually be paths.

Cheers
Ben




More information about the darcs-devel mailing list