# Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $$G=(V,E)$$ be an unweighted directed acyclic graph with a set $$V$$ of vertices and a set $$E$$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall algorithm. The new objective is to find a subset of maximum cardinality $$S \subseteq V$$ such that for every pair of vertices $$v$$ and $$u$$ in $$S$$, the length of the shortest path from $$v$$ to $$u$$, if it exists, is greater than or equal to a positive natural number $$k$$.

This problem could be stated as a bottleneck capacity maximization problem in a complete directed weighted graph. You are given a complete weighted directed network and the objective is to find an induced subgraph with $$m$$ vertices where the minimum arc capacity is greater than or equal to $$k$$.

The reduction gives the arc from $$v$$ to $$u$$ a weight equal to the shortest path computed by Floyd-Warshall from $$v$$ to $$u$$ (if there is no path, a weight of $$\infty$$ is given). Is there an efficient/polynomial time dynamic programming approach to solve the problem?

• – D.W.
Commented Mar 22 at 4:33
• @NealYoung I hadn't considered that special case, I've modified the post. On a side note, would the undirected complete weighted graph problem also exhibit the same complexity? Commented Mar 25 at 15:32
• My answer below was originally for the undirected weighted case. In that case essentially the same reduction from Max Independent Set shows hardness of approximation. However there is a bicriteria approximation (see Lemma 2 there). Commented Mar 25 at 20:23
• @NealYoung I see, that's right. Commented Mar 26 at 11:30

[EDIT: updated answer to apply to directed acyclic graphs.]

Lemma 1. This problem is equivalent, under approximation-preserving poly-time reductions, to Maximum Independent Set in undirected graphs.

Independent Set is NP-complete and NP-hard to approximate within a factor of $$n^{1-\epsilon}$$ (for any $$\epsilon>0$$), so so is this problem:

Corollary 1. The problem is NP-complete and NP-hard to approximate within a factor of $$n^{1-\epsilon}$$ for any $$\epsilon>0.$$

Proof of Lemma 1. First we describe the reduction from Max Independent Set. Given an instance $$G=(V, E)$$ of Max Independent Set, the reduction outputs the directed graph $$G'$$ obtained from $$G$$ by directing each edge so that $$G'$$ is acyclic (e.g. arbitrarily order the vertices, then orient $$(u, v)$$ from $$u$$ to $$v$$ if $$u$$ comes before $$v$$ in the ordering), and take the "distance budget" $$k$$ to be $$2$$.

To see that the reduction is correct, note that a given vertex subset $$S$$ is an independent set in $$G$$ iff no two vertices in $$S$$ share an edge, which holds iff no two vertices in $$S$$ are at distance 1 in $$G'$$.

Next we describe the reduction to Max Independent Set. Given an instance $$(G=(V, E), k)$$ of OP's problem, construct the undirected graph $$G'=(V, E')$$ where $$E'= \{\{u, w\} \subseteq V : d(u, w) < k\}$$. Then a vertex subset $$S$$ is an independent set in $$G'$$ iff it contains no two vertices of distance less than $$k$$ in $$G$$. $$~~~\Box$$

For the variant in undirected graphs, there is a bicriteria approximation algorithm:

Lemma 2. For the variant with undirected graphs, in poly time one can compute a set $$S_k$$ achieving minimum distance $$k$$, with size at least the maximum size of any set $$S^*_{2k}$$ achieving distance at least $$2k$$.

Proof of Lemma 2. The algorithm is greedy: choose any vertex to add to $$S_k$$, delete all vertices within distance strictly less than $$k$$ from the vertex, and repeat until the graph is empty.

Each "ball" of deleted vertices contains at most one vertex from $$S^*_{2k}$$, so $$|S_k| \ge |S^*_{2k}|$$. $$~~~~\Box$$

For OP's problem, with directed acyclic graphs, the greedy algorithm in Lemma 2 doesn't guarantee such a good bicriteria approximation.

• Thank you for your insightful answer! The reduction you gave is partly correct, the resulting graph isn't necessarily a directed acyclic graph. Commented Mar 23 at 1:06
• Oops, I missed that. I've updated the hardness result in the answer. Commented Mar 23 at 13:44