3
$\begingroup$

Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything.

I am also given a collection of assertions. Each assertion takes the form $s_1<s_2<\cdots<s_m$, where $s_1,\dots,s_m$ form a subset of the symbols of $S$. The assertion probably won't mention all of the symbols of $S$, just a subset. Each assertion will probably cover a different subset.

Warmup problem. The starter problem is: Given $n$ assertions, identify whether they are all internally self-consistent, i.e., whether there exists a total order on $S$ that is consistent with all of the assertions, and if so, output an example of such a total order.

The real problem. In practice, a few assertions might be faulty. Almost all of them should be correct, though. So, the real problem is: if the assertions are not all internally self-consistent, find a minimal subset of assertions to label as "probably-erroneous", such that if you remove the probably-erroneous assertions, the remainder are all self-consistent.

What I know. I know how to solve the warmup problem (just compute the transitive closure of the union of the partial orders given by each assertion, and check that the result is antisymmetric; or, in other words, create a graph with $S$ as vertex set and an edge $s\to t$ if $s<t$ appears in any assertion, then check for cycles). However, I don't know how to solve the real problem. Any ideas?

Real-world parameters. In the application domain where I've run into this, $S$ might have up to a few hundred symbols, and I might have up to a few thousand assertions, with each assertion typically mentioning dozens of symbols.

$\endgroup$
  • $\begingroup$ I suppose this is implied, but you are looking for an efficient algorithm for this problem, not just any (brute-force) algorithm, right? $\endgroup$ – Patrick87 Oct 19 '12 at 18:10
  • $\begingroup$ Correct, I'm looking for a reasonably efficient algorithm. I would be satisfied with an approximation algorithm (one that may not find the exact-minimum set of "possibly-erroneous" assertions, if the size of the set it outputs is usually not too much larger than the minimum). $\endgroup$ – D.W. Oct 20 '12 at 1:41
3
$\begingroup$

This sounds like weighted FAS (Feedback Arc Set). Find a minimal (weight) feedback arc set in a directed graph and report the assertions that contributed to the wrongly directed arcs.

For each pair of symbols s and t, there is an arc saying how many assertions have s < t and how many assertions have t < s.

This is a known NP-complete problem.

On a different note, your problem is a classic social choice problem where each of the "assertions" are votes.

$\endgroup$
  • $\begingroup$ Brilliant! Algorithms for weighted FAS do sound like just the sort of thing I was looking for. This search term should be a great start to help me look for approximation algorithms for FAS. Thank you! Do you have any advice regarding approximation algorithms or heuristics for weighted FAS that are good candidates to try, for a practical application? (Simple schemes would be nice.) $\endgroup$ – D.W. Oct 20 '12 at 1:51
  • $\begingroup$ This is indeed an interesting question, and as Jonas says, it resembles FAS and has relations to social choice theory. However, it is a generalization to FAS, and I believe that the problem is potentially much harder than FAS. To say that it generalizes FAS, you simply let S be the vertices of a graph and your linear orders the set of edges (each order has size 1). Now, FAS was (relatively) recently shown to be FPT, i.e., solvable in time f(k)*poly(n), but this was a long standing open problem. I am afraid this problem is not easily solvable. (k is the number of orders you must delete.) $\endgroup$ – Pål GD Oct 27 '12 at 15:23
2
$\begingroup$

I thought I'd jot down the two approaches that have occurred to me, but maybe you can do better.

Approach 1. Here's a randomized procedure that, given an ordering of the assertions, will emit a candidate set of assertions labelled as "probably-erroneous" such that the remainder are all self-consistent. We can repeat the procedure many times, and keep the best output (the one with the smallest number of assertions labelled as "probably-erroneous").

The procedure:

  • Step 1. Randomly permute the assertions. Create an empty graph $G$ with vertex set $S$ and with no edges
  • Step 2. For each assertion, in the order chosen in step 1, do the following:

    • Suppose the assertion is $s_1<s_2<\cdots<s_m$. Test whether adding the edges $s_1\to s_2, \dots, s_{m-1} \to s_m$ would create a cycle in $G$.
    • If this would create a cycle, label this assertion as "probably-erroneous", and don't add the edges to $G$.
    • If this would not create a cycle, add the edges to $G$.

Approach 2. Create a $|S|\times|S|$ matrix $V[\cdot,\cdot]$, where $V[s,t]$ counts the number of "votes" for the claim $s<t$. Initialize all counts in the matrix to zero.

Treat the assertion $s_1<s_2<\cdots<s_m$ as a collection of $m(m-1)/2$ votes for the claims $s_1<s_2$, $s_1<s_3$, $s_2<s_3$, etc. Process each assertion, incrementing the counts in $V$ appropriately. This gives you the full matrix $V$.

Now look through $V$ to check for symbols $s,t$ such that $V[s,t]>0$ and $V[t,s]>0$ and such that the quantity $V[t,s]/(V[s,t]+V[t,s])$ is minimized. Conclude that $s<t$ is correct, and label all assertions which contradict this (which voted for $t<s$) as "probably-erroneous". Remove these assertions from the set of assertions, and re-start the entire procedure, until the assertions that remain are all self-consistent.

This procedure is not guaranteed to terminate with a correct answer (e.g., consider the five assertions $A<P$, $P<Z$, $A<Q$, $Q<Z$, $Z<A$), but it's a heuristic that might be worth trying.

$\endgroup$
  • $\begingroup$ Again, are you looking for (a) a known correct algorithm, regardless of cost; (b) a known correct algorithm which is optimal or significantly better than brute-force; or (c) an efficient heuristic that does pretty well most of the time? $\endgroup$ – Patrick87 Oct 19 '12 at 18:57
  • $\begingroup$ Yes. :-) I'll take whatever I can get. The only hard requirement is that it be efficient (feasible to run within, say, a few minutes or hours). An efficient heuristic that does pretty well most of the time might be perfectly satisfactory. Of course, if you can do better than that, so much the better! (Obviously, there is a trivial solution that is guaranteed-correct but is very slow: simply enumerate all $2^n$ subsets of assertions. I'm ruling that one out because it's too slow to run in practice.) Sorry to be a bit vague and open-ended! $\endgroup$ – D.W. Oct 20 '12 at 1:46

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.