We a have polytree $G = (V, E)$. Note that every vertice $v_i$ can only have one outgoing edge.
Now lets add a new type of edge which we call an red edge. $R$ is the set of all these edges.
So we have a new graph $G = (V, E, R)$. My goal is to find a order $O = v_1, ..., v_n$, which is
- $(v_i, v_j) \in E$, $i < j$ (Just like a regular topological order)
- $(v_i, v_j) \in R$, $i < j$ OR $i > z$ if there exists an edge $(v_i, v_z)$. Which is to say for every red edge $(v_i,v_j)$ then $v_i$ must either come before $v_j$ or after $v_j$'s child in the order
Lets call such an order a red topological order.
For example:
Here a red topological order would be 2130 while 3210 is a topological order but it does not satisfy the condition for the red edge (2,3) as 2 comes inbetween 3 and 0.
We can note that if any of the following is true for a graph $G$ then it has no red topological order:
$R$ contains a cycle between nodes with a common child
$R$ contains $(v_i, v_j)$ and $(v_j, v_i)$ AND if they share a common grandchild $v_x$ then $R$ contains $(v_i, v_y)$ where $v_y$ is every regular edge between $v_j$ and $v_x$. For example, in the figure below $R$ contains $(2, 3)$ and $(3, 2)$. Their common grandchild is $0$. $1$ is the node between $2$ and $0$. $R$ contains $(3, 1)$. As we can see the graph has no red topological ordering.
So we know that if G has a red topological order $\implies$ $(1)$ and $(2)$ is not true for G which I dont have a problem proving. My suspicion is that if $(1)$ and $(2)$ is not true for $G$ $\implies$ $G$ has a red topological order
This would be nice to prove because then we know that if (1) and (2) is not true for $G$ $\iff$ $G$ has a red topological order.
My two questions is:
- How would I go on to prove or disprove that if $(1)$ and $(2)$ is not true for $G$ $\implies$ $G$ has a red topological order?
I could disprove it by finding a graph G where (1) and (2) is not true BUT still has no red topological order, but I haven't been able to do that.
Ive tried proving it similar to how one proves that if a graph is a DAG then it has a topological order. But Ive only found proofs by induction and cant to do this in my case.
And thirdly Ive tried this strategy:
$G = (V, E, \emptyset)$. Let $A = $ all graphs that can be created by adding red edges to $G$ with atleast one red topological order. Let $B = $ all graphs created by adding red edges to $G$ where (1) and (2) is not true.
Then I want to prove that $A = B$ by proving that $A \subseteq B$ and $B \subseteq A$. Proving $A \subseteq B$ is no problem as this is the same as proving G has a red topological order $\implies$ $(1)$ and $(2)$ is not true for G
But proving $B \subseteq A$???
- Can I formulate the problem differently so it is easier to prove?