How to find whether there is a contradiction in a graph

Question

I have a historical record that indicates the relative order of births and deaths. The format of these records are always in one of the following

• Person A was alive with Person B
• Person B died before Person A was born

For example

A was alive with B
C died before B was born
E died before D was born
E died before B was born
D was alive with B
D died before F was born
A was alive with E
F died before G was born
G died before D was born
A died before G was born
G was alive with C

yield this network:

We can see that there is a contradiction because D<F<G but D>G. More generally, what should I be looking for to find whether there is a an inconsistency in the graph? I can sort of understand how to do it with inequalities D<F<G<D which yields a cycle, but am more confused how to logically fuse in the equalities.

Answer 1

It is more convenient to represent each person $A$ by two vertices: their time of birth $A_b$, and their time of death $A_d$. Then, add an edge $u \to v$ whenever vertex $u$ is known to come before vertex $v$ chronologically:

• Initially, we add all edges of the form $A_b \to A_d$.
• Whenever $A$ and $B$ are alive at the same time, we add the edges $A_b \to B_d$ and $B_b \to A_d$.
• Whenever $A$ dies before $B$ is born, we add the edge $A_d \to B_b$.

In the actual (but unknown) timeline, these vertices are ordered (from earliest event to latest event) such that whenever $u \to v$, $u$ occurs before $v$. This is a topological ordering of the directed graph we got. If there are no cycles in the directed graph, then at least one topological ordering exists: at least one timeline consistent with all the facts we have.

As mentioned in the Wikipedia article I linked to above, there are fast algorithms that will either

• find a topological ordering of the directed graph, in which case there is no contradiction, or
• find a directed cycle in the graph, in which case there is a contradiction.

Answer 2

Edit: If, as mentioned in comments, you want the "lived at the same time" relationship to be treated as an equivalence relation, contrary to all intuition, then you can just take a directed graph. $G,$ with nodes being the equivalence classes of people under this relationship, and edge $(x,y)$ when some person in the class $x$ lived strictly before some person in the class $y.$

Then the question is whether there is any loop in $G.$ This has a simple algorithm.

---

Original Answer

Not sure if this is the ideal approach, but if there are $n$ people define an $n\times n$ matrix $A$ with $$A_{ij}=\begin{cases}1&i\text{ died before birth of }j\\0&\text{otherwise}\end{cases}$$

Then compute $$B=\sum_{i=1}^\infty \lambda^iA^i=A(I-\lambda A)^{-1}.$$ We can do this for some $\lambda>0$ small. Then find any $B_{ij}\neq 0$ with $i,j$ Where persons $i,j$ lived in the same time (including all cases where $i=j.$) If there is such a $B_{ij},$ there is a contradiction.

Not sure if there is an efficient way to do this. You need $\lambda^{-1}$ to be greater than the absolute values of all eigenvalues of $A,$ but there might be an algebraic way to avoid picking a specific $\lambda.$