2
$\begingroup$

Given a fully connected graph $G(V,E)$ with associated edge weights and a set of constraints specifying distance $D(V_i, V_j) < M_{ij}$, where $\left\{V_{i..j}\right\} ⊂ V$, how can I go about finding the smallest subset graph $G'(V', E')$ such that none of the constraints are violated?

In other words, find the smallest subset of the graph such that the distance between a given set of vertices does not exceed some constant.

$\endgroup$
  • $\begingroup$ Do you want the resulting graph to have the minimum total number of edges, or the set of edges having minimum possible weight? $\endgroup$ – j_random_hacker Oct 19 '16 at 13:52
  • $\begingroup$ What do you mean by "$\{V_{i..j}\}\subset V$"? $\endgroup$ – David Richerby Oct 19 '16 at 15:58
  • $\begingroup$ @j_random_hacker minimum number of total edges. $\endgroup$ – Amit Ambasta Oct 19 '16 at 18:20
  • $\begingroup$ @DavidRicherby I meant that the distance constraint b/w Vi, Vj exists for some vertices in V (but not all) $\endgroup$ – Amit Ambasta Oct 19 '16 at 18:22
  • $\begingroup$ @AmitAmbasta I don't understand what you mean by that, or how it relates to the notation you used. $\endgroup$ – David Richerby Oct 19 '16 at 18:41
4
$\begingroup$

This is NP-hard by reduction from Set Cover. The problem remains NP-hard even if edge weights are restricted to $\{1, 3\}$.

In the Set Cover problem, we are given a ground set $U$ containing $m$ elements $x_1, \dots, x_m$, a collection $\mathbf S$ of $n$ subsets $S_1, \dots, S_n$ of $U$, and an integer $k$, and our task is to determine whether there exists some set of at most $k$ of the $n$ sets in $\mathbf S$ whose union contains all $m$ elements in $U$.

First let's frame your problem as a decision problem: Given an edge-weighted undirected graph $G = (V, E)$, a set of $r$ constraints $d(v_{s(i)}, v_{f(i)}) \le M_i$ for $1 \le i \le r$ and an integer $q$, does there exist a subgraph $G'$ of $G$ such that each constraint is satisfied by some path in $G'$ and $G'$ contains at most $q$ edges?

To convert a given Set Cover instance into an instance of this problem:

  1. Create a vertex $t$.
  2. For each element $x_i$, create a vertex $u_i$ and the constraint $d(u_i, t) \le 2$.
  3. For each set $S_j$, create a vertex $v_j$ and the unit-weight edge $v_jt$.
  4. For each $x_i$ that belongs to a set $S_j$, create the unit-weight edge $u_iv_j$.
  5. Add in all possible remaining edges, giving each weight 3.
  6. Set $q$ to $m+k$.

First, suppose the solution to the Set Cover problem is YES. It is easy to construct a solution to the constructed instance of your problem: For each set $S_j$ not selected by the Set Cover solution, delete the corresponding edge $v_jt$. For each element $x_i$, choose some set $S_j$ such that $x_i \in S_j$ and $S_j$ was selected by the Set Cover solution (since the solution was YES, such an $S_j$ must exist) and keep the corresponding edge $u_iv_j$; delete all other edges incident on $u_i$. Finally, delete all weight-3 edges. Clearly this leaves exactly $m$ edges incident on $u$-vertices, plus at most $k$ edges connecting $v$-vertices to $t$, for a total of at most $q = m+k$ edges. Each $u_i$ is connected to $t$ by a length-2 path via the vertex $v_j$ corresponding to its chosen containing set $v_j$, so all distance constraints are satisfied. Thus the solution to the constructed instance of your problem is also YES.

Second, suppose that the solution to the constructed instance of your problem is YES. Let $G'$ be any such satisfying subgraph.

Since $G'$ satisfies all distance constraints, and no weight-3 edge can participate in any such path, removing any remaining weight-3 edges in $G'$ must produce another valid solution $G''$.

Every $u$-vertex in $G''$ is adjacent to some $v$-vertex that is adjacent to $t$, since the answer to the problem was YES and there are no other paths from $u$-vertices to $t$ of distance $\le 2$. Suppose some $u_i$ in $G''$ is incident on 2 or more outgoing edges. All but one of these edges can be removed without violating the $d(u_i, t) \le 2$ constraint. Let $G'''$ be the graph that results from performing these edge deletions on $G''$: $G'''$ is a valid solution.

Each of the $m$ $u$-vertices in $G'''$ is incident on exactly 1 edge, and since the answer to the problem was YES, the total number of edges in $G'''$ is $\le q = m+k$, so there are at most $k$ other edges in $G'''$. These can only be edges between $v$-vertices and $t$. Construct a solution to the original Set Cover problem by selecting the at most $k$ sets corresponding to the $v$-vertices that are adjacent to $t$ in $G'''$: clearly the union of these sets contains all $m$ vertices, so the answer to the original Set Cover problem is also YES.

We have established that a YES answer to each problem implies a YES answer to the other problem, so a NO answer to either problem implies a NO answer to the other one, so the problems are equivalent. The constructed instance of your problem is easily constructed in polynomial time, so it follows that your problem is NP-hard.

$\endgroup$
0
$\begingroup$

This problem is NP-hard problem, you should go with heuristics or meta-heuristics, to find acceptable solution in acceptable time. try first Genetic algorithms, they are very powerful and they will give you great ideas.

$\endgroup$
  • $\begingroup$ Any reading material which you could recommend for this class of problems? $\endgroup$ – Amit Ambasta Oct 19 '16 at 11:10
  • 5
    $\begingroup$ Please add either a proof or a reference of NP-hardness. $\endgroup$ – adrianN Oct 19 '16 at 11:16
  • 1
    $\begingroup$ You should edit your answer instead of leaving a comment. $\endgroup$ – Evil Oct 19 '16 at 15:11
  • $\begingroup$ @AmitAmbasta This may be a good place to start. $\endgroup$ – Raphael Oct 19 '16 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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