2
$\begingroup$

Let $G=(V,A)$ be a simple directed acyclic graph. A set consisting of two vertices is called dependent if there is a directed path from one of the vertices to the other. The question is to find directed paths $\{P_1,\ldots,P_m\}$ of minimum $m$ such that any pair of dependent vertices belongs to at least one path $P_i$ for some $i$.

I have no idea how to solve this or how to transform this problem to a known problem.

$\endgroup$
5
  • $\begingroup$ Possibly relevant question: mathoverflow.net/questions/242777/… $\endgroup$ Commented Feb 4, 2018 at 22:12
  • 2
    $\begingroup$ I'm confused by "minimum length $m$". Do you want to minimise the number of paths or the length of them? $\endgroup$ Commented Feb 5, 2018 at 4:02
  • 1
    $\begingroup$ I want to minimize number of paths. $\endgroup$
    – Moshe
    Commented Feb 5, 2018 at 10:00
  • $\begingroup$ I posted my answer to the same question here cstheory.stackexchange.com/a/40243/36593. $\endgroup$
    – Ce Jin
    Commented Feb 22, 2018 at 1:48
  • $\begingroup$ @Ce Jin, thanks, but I think your solution is not correct! $\endgroup$
    – Moshe
    Commented Feb 22, 2018 at 21:10

1 Answer 1

1
$\begingroup$

An answer via hypergraph theory

There exists an obvious reduction to the minimum edge cover problem in hypergraph theory (also known as the set cover problem). I will describe this reduction.

A word of caution upfront: this approach is probably too heavy-handed in that the hypergraphs which arise are very special, and to apply general-purpose hypergraph-algorithms to these special auxiliary hypergraphs is probably a waste. I have a feeling that some graph-theoretic approach exploiting the specifics of the problem will be much faster.

Definitions. Let $[S]^2$ denote the set of two-element subsets of any set $S$, and for any digraph $G$,

  • let $\mathsf{Dependent}(G)\subseteq [V(G)]^2$ denote the set of dependent vertices, in the OP's sense,

  • let $\mathsf{MaximalPaths}(G)$ denote the set of all directed paths in $D$ which are not properly contained in another directed path.

Define a map $F\colon \mathsf{SimpleAcyclicDigraphs}\rightarrow\textsf{SimpleHypergraphs}$ by letting $F(G)=(N,M)$ be the hypergraph with ground set $N:=\mathsf{Dependent}(G)$ and edge-set $M:= \{ [V(P)]^{2}\colon P\in\mathsf{MaximalPaths}(G) \}$, where $V(\cdot)$ denotes the vertex-set of a digraph, and $[.]^2$ the set of all two-element subsets of a set.

Lemma. If $\{P_1,\dotsc,P_m\}$ is a cover as required in the OP, then there exists such a cover $\{P_1',\dotsc,P_{m'}'\}$ such that $m'=m$ and each $P_i'\in\mathsf{MaximalPaths}(G)$.

Proof. It suffices to replace each non-maximal $P_i$ with an arbitrary maximal directed path $P_i'\supseteq P_i$. Since already $\{P_1,\dotsc,P_m\}$ is a cover of the set of dependent pairs of vertices, so is $\{P_1',\dotsc,P_m'\}$. This proves the lemma.

An answer to the question "transform this problem to a known problem" in the OP.

Proposition. Any minimum vertex cover $C$ of the hypergraph $F(G)$ yields a set $S(C) = \{P_1,\dotsc,P_m\}$ of the kind requested in the OP, as follows: write $C=\{E_0,\dotsc,E_{m-1}\}$, and for each $i\in m$ let $P_i$ denote the unique directed graph with vertex set $\cup E$ and edge-set the set of directed edges obtained by giving each two-set in $E$ the orientation that the corresponding eddge of $G$ has. (In other words, $P_i$ is the directed path in $G$ whose underlying undirected graph has edge-set equal to $E_i$.) In particular,

$m = \rho(F(G))\hspace{250pt}$ (eq)

which gives some sort of answer to the OP. (Again, probably not the best answer.)

Remark. Here, 'minimum edge cover' and $\rho$ have the usual meaning from hypergraph theory, cf. e.g. [Berge: Hypergraphs. Elsevier 1989, ISBN: 0444874895, p. 64]; I recall the counter-intuitive but deeply entrenched convention that 'edge cover' means 'cover-of-the-ground-set-by-edges'.

Proof. Let any minimum edge cover $C$ of $F(G)$ be given. Let $S(C)=\{P_1,\dotsc,P_m\}$ be constructed as above. We have to prove three statements: (eq), and (0) every pair of dependent vertices is contained in one of the $P_i$, and (1) there does not exist any cover $\{P_0',\dotsc,P_{m'-1}'\}$ with $m'<m$. As to (eq), this holds by construction of $S(C)$. As to (0), let any $uv\in\mathsf{Dependent}(G)$ be given. Because of $N=\mathsf{Dependent}(G)$, and because $C$ by definition is an edge-cover of the ground-set $N$, there exists $i\in m$ such that $E_i\in C$ and $uv\in E_i$. This implies $uv\in V(P_i)$, where $P_i$ is as in the penultimate paragraph. This proves (0). As to (1), suppose there were such $\{P_0',\dotsc,P_{m'-1}'\}$. For each $i\in m'$ replace $P'_i$ with an arbitrary maximal directed path $\widetilde{P'_i}\supseteq P'_i$. The, by definition of the hypergraph $F(G)$, each of the sets of two-sets $[V(\widetilde{P'_i})]^2$ is a hyperedge of $F(G)$, and by choice of $\{P_0',\dotsc,P_{m'-1}'\}$, the set of these sets of two-sets is an edge-cover; therefore, $m'<m$ is impossible. This proves $\{P_0',\dotsc,P_{m'-1}'\}$ impossible. This completes the proof of the proposition.

Remark on the question "how to solve this". Because of the above reduction, any algorithm for the minimum edge cover problem in hypergraphs (synonym: set cover problem) can be used to solve the OP's problem. However, the reduction from a given simple acyclic digraph to the relevant hypergraph, as I have described it, required the computation of the set of all maximal directed paths, and this is costly. This is one of the reasons why I think that my suggestion is not the best one. An overview of complexity results regarding the minimum set cover problem as of roughly the year 2000 can be found here.

The set of all maximal directed paths in digraph can be computed by an easy algorithm which resembles breadth-first search. It is sketched on page 418 of

Harold Parks, Gary Musser, Lynn Trimpe, Vikki Maurer, Roger Maurer: A Mathematical View of Our World. Cengage Learning, 2006 ISBN 9780495010616

Caution: the method I have recommended has worst-case time-complexity exponential in the order of the graph, already because of the strong reason that there are many digraphs which contain exponentially many maximal directed paths: e.g., by a theorem of T. Szele there exist tournaments on $n$ vertices containing at least $\frac{n!}{2^n}$ $\geq$ $\sqrt{2\pi n}\cdot(\frac{n}{2\mathrm{e}})^n$ distinct directed Hamilton paths (and hence at least as many maximal directed paths), and by [Ilan Adler, Noga Alon, Sheldon M. Ross: On the Maximum Number of Hamiltonian Paths in Tournaments, Random Structures and Algorithms 18(3), 2001, 291-296], Szele's bound can be improved to a little less than $\mathrm{e}\cdot \frac{n!}{2^{n-1}}$. So even to list all the maximal paths (which my inefficient recommendation requires) can happen to take exponentially many steps.

Remark on how special the hypergraphs involved in the above approach are.

The subclass $\{ F(G)\colon G\in\mathsf{SimpleAcyclicDigraphs} \}\subset\mathsf{SimpleHypergraphs}$ is very special (hence hitting it with general-purpose hypergraph algorithms is a rather callous modus operandi, not to speak of the preprocessing overhead already mentioned). In particular, each such hypergraph has all its hyperedges of cardinality $\binom{k}{2}$ for some $k\in\omega$. In particular, no nontrivial such hypergraph is an abstract simplicial complex. And I also doubt that even among the special class of hypergraphs all of whose hyperedges have cardinality $\binom{k}{2}$, those which arise as $F(G)$ for $G$ a simple acyclic graph are yet more special (though I haven't thought about it).

Thus, if this is very important to you, than you should look into the literature on the minimimum set cover problem, and adapt what you find to this special class of hypergraphs. In particular, although the minimum set cover problem is NP-hard in general, I doubt that the hardness persist when restricting to these special hypergraphs of the form $F(G)$. In particular, note that the usual proof of NP-hardness of the minimum set cover problem procedes by polynomially reducing from minimum vertex cover problem, by considering the hypergraph of stars centered at the vertices of the given graph, and for this proof to work, one has to have available a general algorithm for minimum set cover (because the stars at the vertices have no general reason to only have sizes $\binom{k}{2}$). Thus, the only proof of hardness of the relevant hypergraph problem fails when restricted to this special class of hypergraphs.

Example. The simple acyclic digraph $G$ represented by

enter image description here

is mapped by $F$ to the simple hypergraph whose Levi graph is represented by

enter image description here

and the only minimum edge cover of $F(G)$ is $\{ \color{green}{\text{$E_2$}},\color{blue}{\text{$E_3$}} \}$. Incidentally, the edge $e_2$ not being contained in any of $\color{green}{\text{$E_2$}},\color{blue}{\text{$E_3$}}$ shows that a solution $\{P_1,\dotsc,P_m\}$ as required by the OP need not cover all edges.

Remarks on the pictures. (0) The labels of the arcs of $G$ are rotated for technical reasons (the picture was not drawn manually, and it is more systematic to have the labels rotate according to the direction of the edges), (1) the colors in the representation of $G$ indicate the members of $\mathsf{MaximalPaths}$, (2) $E_1$ is not the edge $e_2$ of the digraph, but the singleton $\{e_2\}$ containing that edge, (3) the colored edges are for easier readability only; this way, it is evident that $\color{green}{\text{$E_2$}},\color{blue}{\text{$E_3$}}$ is a minimal edge-cover of the hypergraph represented by this Levi graph (and it is even evident that it is minimum, for clearly the entire ground-set is not a hyperedge).

A relevant literature recommendation (though perhaps not an answer)

The OP's problem is closely related to an attested research topic which goes by the name minimum equivalent digraph. (There is also an analogue for undirected graphs, for which the relevant keyword is minimum equivalent graph.) Note that

for acyclic digraphs, the minimum equivalent digraph exists, is unique, and is equal to the more widely known transitive reduction.${}\hspace{150pt}$ (note)

In this context, 'equivalent' is a usual but unimaginative way to say 'has the same binary reachability-relation'. (Here, the binary reachability relation of a digraph $G$ is the reflexive, transitive, but in general not symmetric, relation $R\subseteq V(G)\times V(G)$ with $(u,v)\in R$ if and only if $\exists$ directed $u$-$v$-path in $G$.

The minimum equivalent digraph is simply this: given a digraph $G$, find a largest set of edges of $G$ which can be deleted while still leaving the reachability relation of $G$ invariant.

It is known at least since Garey and Johnson's legendary book that to decide whether there is an 'equivalent' (in the above sense) digraph with at most $K$ edges to a given finite digraph is NP-complete if all inputs are arbitrary. Reason: any algorithm $A$ which can do this for general instances, can in particular be used to decide the problem $\textsf{DirectedHamiltonCircuit}$, a well-known NP-complete decision problem, by taking $K:=$order of the given digraph. For more detail, see [M. R. Garey, D. S. Johnson: Computers and Intractibility. ISBN 0716710447. 1979. page 65, item (5)].

However, and this seems somewhat relevant to your specific question, for acyclic digraphs, there exist efficient algorithms for computing a minimum equivalent digraph, see

Harry T. Tsu, An Algorithm for Finding a Minimal Equivalent Graph of a Digraph, Journal of the ACM, Volume 22 Issue 1, 1975, 11-16

Another relevant research article is

Samir Khuller, Balaji Raghavachari, Neal E. Young: Approximating the minimum equivalent digraph. SIAM Journal on Computing 24(4):859-872(1995); also in: SODA'94

You may also find it useful to look into path preserving reductions, cf. e.g. [Alan George,John R. Gilbert,Joseph W.H. Liu, eds. Graph Theory and Sparse Matrix Computation, Springer, 2012, ISBN 9781461383697; Section 6.4].

Now the question is of course how relevant minimum equivalent digraphs are to the OP's problem: it is not even clear a priori whether passing to a minimum equivalent digraph might---while of course it preserves the set of independent vertex-pairs---perhaps increase the value of $m=m(G)$. I haven't looked at examples except for the one example illustrated above; there, only one minimum equivalent digraph exists: $(V(G),E(G)\setminus\{e_0,e_2\})$. (Proof: removing $e_2$ destroys only the length-one path $(\{0,3\},\{e_1\})$, and since there is another directed $0$-$3$-path, actually doing so does not change the set of dependent two-sets; moreover, removing $e_0$ destroys precisely two paths: itself, and $0\to1\to4$, but both these are still taken care of by the path $e_1,e_3,e_5$; moreover, $e_1$ must not be removed since otherwise there wasn't any $0\to 2$-path anymore; moreover, $e_3$ must not be removed since otherwise there wasn't any $2\to1$-path anymore; moreover, $e_4$ must not be removed for otherwise there wasn't any $2\to3$-path anymore; moreover, $e_5$ must not be removed for otherwise there wasn't any $1\to4$-path anymore. This proves that $G':=(V(G),E(G)\setminus\{e_0,e_2\})$ is indeed a minimum equivalent digraph w.r.t. $G$. Moreover, the claim that there is "only one" follows from the uniqueness part of (note). Moreover, passing to this unique minimum equivalent digraph is no harm as far as your problem is concerned: in $G'$, you still find the same required set of paths $\{P_1,\dotsc,P_m\}$, namely the one corresponding to $\{ \color{green}{\text{$E_2$}},\color{blue}{\text{$E_3$}} \}$.

So there is hope that the following question, which seems a reasonable direction you could pursue, has an affirmative answer:

Is it true that for every finite simple acyclic digraph $G$, every set of paths in the OP's sense also arises in the same way if one first reduces to the unique minimum equivalent digraph?

Please note that, so far, the present answer does not provide you with an efficient algorithm. (And it is quite possible that none such exists.) Maybe a closer look at how the OP's problem relates to the minimum equivalent digraph problem will lead to an efficient algorithm.

$\endgroup$
2
  • $\begingroup$ Dear Peter, do you think that $m \leq |A|$? $\endgroup$
    – Moshe
    Commented Mar 1, 2018 at 7:20
  • $\begingroup$ @Moshe: I don't know, sadly. $\endgroup$ Commented Mar 1, 2018 at 7:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .