3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Related: nakano-lab.cs.gunma-u.ac.jp/Papers/Max-Min_3-dispersion.pdf, towardsdatascience.com/… $\endgroup$
    – D.W.
    Commented Mar 22 at 4:33
  • $\begingroup$ @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? $\endgroup$ Commented Mar 25 at 15:32
  • $\begingroup$ 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). $\endgroup$
    – Neal Young
    Commented Mar 25 at 20:23
  • $\begingroup$ @NealYoung I see, that's right. $\endgroup$ Commented Mar 26 at 11:30

1 Answer 1

4
$\begingroup$

[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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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