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.