Construct a DAG from given multiple topological orderings

Question

I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as first $n$ natural numbers. (Note that once created, the graph $G$ may have more topological orderings apart from the ones given.)
The following constraints should be met:

1. The maximum outdegree of every node should be 1
2. The number of nodes having indegree 0 should be minimum.

There can be multiple solutions, any of them should work.

What I have tried. (Approach 1 which is wrong as it fails one example given in the answer. Please scroll to the second approach, which still I'm not able to find a mistake.)

Approach 1
From all the given orderings, first, create a directed graph by creating a directed edge from every node to its next node. This means if the orderings are:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

I will create a directed graph with a directed edge from $1$ to $3, 3$ to $2, 2$ to $5$ and so forth.

This ensures that the number of nodes with indegree 0 remains minimum. Now, I'll remove all the cycles and make sure all the orderings are valid and finally, eliminate all the extra edges any node has. WHile doing so, I'll make sure that if there are two nodes whose edge is coming from the same node, I'll remove the edge from the node having a higher indegree, so that condition 2 is met. The graph constructed then, should look like:

This DAG created, follows both the constraints, and IMO has the minimum number of nodes of indegree as 0, although, it's not proven.

I have coded the approach and it is giving expected results for the use cases I supply, but I know that it is wrong. What am I missing here? Can anyone provide an alternative use case, which fails the above approach?

Approach 2
I create a directed graph $G$ by creating an edge from $a_i $ to $ a_j$ for all $ j > i$ in all the orderings given. So, for the orderings:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$

I will create the following graph:
The first step after this is to validate all the orderings. Removing cycles separately is not required as they will be removed by this step itself.
For any ordering $$ a_1, a_2, a_3, a_4, ... a_n $$ I will check if there exists any edge from $a_j$ to $a_i$ where $ j > i$, I'll remove that edge.
Doing so, will give the following graph:
The last step is to remove extra edges from all nodes as maximum outdegree of any node can be $1$ max. I'll remove the outgoing edges such that the number of nodes having indegree $0$ is minimum. First I calculate the indegree of each node. Then for each node which has more than 1 outgoing edges, I'll remove all the edges except the one with the minimum indegree.

The final graph $G$ will look like:

This graph satisfies both the constraints. But I know this approach is wrong! Can anyone help to find why is this wrong?

Answer 1

Approach 1

For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3.

According to your approach, we will get a cycle 1->2->3->4->1. We then remove 3->4 and 4->1, and obtain a graph:

     ______
    /      \
1->2->4->5->3
 \______/

Now 5->3 and 1->2 respectively violate the first and the second orders, so we remove them, and get

     ______
    /      \
1  2->4->5  3
 \______/

Now node 2 has 2 outgoing edges. Removing either one makes a final graph where 3 nodes (1, 2, 3 or 1, 2, 4) have in-degree 0.

However, there exists a graph

1->3 2->4->5

where both orders are satisfied but only 2 nodes have in-degree 0.

So Approach 1 is incorrect.

Approach 2

Consider an optimal solution. Every edge in this optimal solution must be the form $(a_i,a_j)$ where $i<j$ in each order. This means all edges in the optimal solution are contained in the intermediate graph. So if you then remove the outgoing edges such that the number of nodes having in-degree 0 is minimum, you will get a correct optimal solution.

However, your approach that trying to make the number of nodes having in-degree 0 minimum is incorrect.

For example, consider the three orders: \begin{align} 1, 2, 3, 4, 5, 6, 7, 8 \\ 5, 1, 6, 3, 8, 2, 4, 7 \\ 2, 7, 3, 8, 1, 4, 5, 6 \end{align}

First we can obtain the following intermediate graph:

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

Applying your approach, we will remove 1->4, 2->4 and 3->4 (or 3->8), and there are 5 nodes with in-degree 0: 1, 2, 3, 4 (or 8), 5. However, the optimal solution would be

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

where only 4 nodes have in-degree 0: 1, 2, 3, 5.