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.
Given many partial orders, check them for consistency and report any that are not consistent
algorithms;graphs;approximation;finite sets;partial order