patternMinor
Given many partial orders, check them for consistency and report any that are not consistent
Viewed 0 times
consistentareanyandreportthatfororderspartialmany
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#6173, answer score: 3
Revisions (0)
No revisions yet.