Finding subgraph in DAG in which all nodes are smaller than all others

Question

I think my problem might be one of terminology, so let me explain what I am trying to do.

Given a direct acyclic graph $G$ interpreted as a partial order, I want to find a subgraph $S$, so that $\forall v \in S, \forall w \in G \setminus S: v < w$.

Preferably, there would be an algorithm that would find these subsets recursively, if they exist.

Answer 1

Let $(P,\leq)$ be a finite poset and write $n = |P|$. Furthermore, ket $\mathcal T$ denote the family of all $S\subseteq P$ satisfying the criterion (for all $x\in S$ and all $y\notin S$ we must have $x < y$). Note that $\mathcal T$ is a chain with respect to inclusion: if we have $S,T \in \mathcal T$ with $S \not\subseteq T$ and $T\not\subseteq S$, then there exist $x\in S\setminus T$ and $y\in T\setminus S$, but now we have $x < y < x$. This is a contradiction, so we must have $S \subseteq T$ or $T \subseteq S$. Furthermore, we clearly have $\varnothing,P\in\mathcal T$. It follows that $\mathcal T$ has at most $n + 1$ elements.

I shall give an outline of an $\mathcal O(n^2)$ algorithm that lists all elements of $\mathcal T$. I could type up a C++ implementation, should you be interested. The basic algorithm is as follows:

1. Construct a directed graph $H$ with the elements of $P$ as vertices and a directed edge $(u,v)$ going from $u$ to $v$ if and only if $u \not\leq v$ (that is, either $u$ and $v$ are incomparable or $u > v$ holds). This should be interpreted as follows: if $S\in\mathcal T$ meets the criterion, $u\in S$ is a vertex and there exists a directed path from $u$ to $w$ in $H$, then $w\in S$ must hold as well (since every element along the path must also be an element of $S$). Now we can prove that the elements of $\mathcal T$ are precisely the upwards closed sets in $H$:

   • By the preceding remark, every $S\in\mathcal T$ is upwards closed.
   • Conversely, suppose that $S\subseteq P$ is upwards closed in $H$. If $u\in S$ and $v\notin S$ holds, then there is no path in $H$ going from $u$ to $v$, so in particular there is no directed edge going from $u$ to $v$. It follows that $u \leq v$ holds. As we have $u\in S$ and $v\notin S$, we must have $u \neq v$, hence $u < v$.

   This step takes $\mathcal O(n^2)$ time.

2. Find the strongly connected components of $H$ and topologically sort them. The strongly connected components form a DAG, which I shall refer to as the quotient DAG. For all $u,v\in P$ with $u\neq v$, at least one of the edges $(u,v)$ or $(v,u)$ must be in $H$, for otherwise we would have $u \leq v \leq u$, contrary to the assumption that $u \neq v$ holds. Thus, the quotient DAG is a directed path. (Another way to look at it: this is because the elements of $\mathcal T$ form a chain under inclusion.) This step takes $\mathcal O(n + m)$ time, where $m$ is the number of edges in $H$. (We have $m \leq n^2 - n$, so this step also takes $\mathcal O(n^2)$ time.)

3. Iterate backwards through the quotient DAG in order to determine the upwards closed sets. Note that any upwards closed set of $H$ must be the union of strongly connected components. That is, if $C$ is strongly connected component of $H$ and we have an upwards closed set $S\in\mathcal T$ containing some $u\in C$, then we must have $C \subseteq S$, since every element of $C$ can be reached from $u$. Thus, the elements of $\mathcal T$ are precisely the upwards closed sets of the quotient DAG. This step takes $\mathcal O(n)$ time (if we only want to count the number of elements of $\mathcal T$) or $\mathcal O(n^2)$ time (if we want to list every member of $\mathcal T$). Don't forget to list $\varnothing$ and $P$.

Note that the worst-case time complexity is optimal: merely reading the input already takes $\mathcal O(n^2)$ time. Furthermore, if $P$ is linearly ordered, then we have $|\mathcal T| = n + 1$. Listing all elements of $\mathcal T$ will now take $\mathcal O(n^2)$ time as well.

As a final remark, should the input be given as a directed graph instead of a partial order, then we would have to compute the transitive closure first, which takes $\mathcal O(n^3)$ time. This becomes a bottleneck in the performance of the algorithm. I don't think that there is any way around that, but I'm not entirely sure...

Answer 2

In general, the DAG need not have any such sub-graph, if you are looking for a proper sub-graph. A single example suffices:

$$G = \{A,B,C,D\},\qquad\text{with relations}\ A>B,\ A>C,\ D>B$$

Since $C$ and $D$ are not order-comparable, $S$ would have to contain both $D$ and $C$. But the only sub-graph of $G$ satisfying the criterion and containing both $D$ and $C$ is $G$ itself.