patternMinor
Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs
Viewed 0 times
maximumacyclicvertexwithgraphsminimumdistancedirectedrequirementpairwise
Problem
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?
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?
Solution
[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.
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.
Context
StackExchange Computer Science Q#167213, answer score: 4
Revisions (0)
No revisions yet.