3
$\begingroup$

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.

enter image description here

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: enter image description here

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: enter image description here
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: enter image description here
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: enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ Your conditions seem to be completely unrelated to the topological orderings. A path on $n$ nodes meets both conditions and minimizes the number of nodes with indegree 0. $\endgroup$ – Steven Mar 11 at 22:08
  • 1
    $\begingroup$ @KunalGupta But every node in a cycle can be $a_1$. In addition, what is the order of the cycles you deal with? $\endgroup$ – xskxzr Mar 12 at 15:33
  • 1
    $\begingroup$ What do you mean by "The DAG constructed should have all the listed orderings"? It is clearly impossible to get a graph $G$ such that all input orderings are valid topological orderings, in general. As an example consider your first two orderings, in the first one $1$ must precede $3$, in the second one $3$ must precede $1$. Can you give a formal definition of the graph you're looking for? $\endgroup$ – Steven Mar 12 at 17:06
  • 1
    $\begingroup$ @KunalGupta. You are right. Your problem always admits at least one solution, i.e., the empty graph on $n$ nodes. I think you should add as a condition that all topological orderings need to be valid orderings for the sought graph $G$. This is not required right now, as stated. You just say that you want to compute $G$ "using" the topological orderings. $\endgroup$ – Steven Mar 12 at 18:46
  • 1
    $\begingroup$ IIUC, another way of stating your problem is: Given a family of $k$ total orders on $n$ objects, construct an $n$-vertex forest of rooted trees (with edges directed towards the root in each tree) in which "$u$ is an ancestor of $v$" implies that $v < u$ in every order, and such that the number of leaves is minimised. If so, you can find all feasible edges (an infeasible edge cannot be in any valid solution) in $O(kn^2)$ time: $(v_i, v_j)$ is feasible iff the statement $v_i < v_j$ holds in all $k$ orders. $\endgroup$ – j_random_hacker Mar 12 at 22:20
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, but I added after that I ensure that after removing cycles, all the logical orderings still hold as valid topological orderings for the graph. So, if there's still any violation, I'll remove the edges. I think, the approach is correct, maybe I am making some error in coding the algorithm. I may be wrong about this, there may be some flaw in the algorithm as well. $\endgroup$ – Kunal Gupta Mar 13 at 22:06
  • $\begingroup$ @KunalGupta Please see my edit. $\endgroup$ – xskxzr Mar 14 at 1:37
  • $\begingroup$ I understood the flaw. I have edited the question to add one more approach, which is simpler, and gives the correct answer for the example you gave. Still, it is wrong .Can you help to find the flaw in that? Thanks! $\endgroup$ – Kunal Gupta Mar 14 at 11:43
  • 1
    $\begingroup$ @KunalGupta Please don't edit the question to change its meaning, otherwise I have to edit my answer again and again, or even worse, if I don't know the answer to your new question, I have to delete my answer. Instead, please post a new question. $\endgroup$ – xskxzr Mar 14 at 11:47
  • $\begingroup$ I have added another approach in addition to the one already given and acknowledged the answer. You don't need to change it. $\endgroup$ – Kunal Gupta Mar 14 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.