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$
6
  • $\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$ Commented Oct 19, 2016 at 13:52
  • $\begingroup$ What do you mean by "$\{V_{i..j}\}\subset V$"? $\endgroup$ Commented Oct 19, 2016 at 15:58
  • $\begingroup$ @j_random_hacker minimum number of total edges. $\endgroup$ Commented Oct 19, 2016 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$ Commented Oct 19, 2016 at 18:22
  • $\begingroup$ @AmitAmbasta I don't understand what you mean by that, or how it relates to the notation you used. $\endgroup$ Commented Oct 19, 2016 at 18:41

2 Answers 2

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

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.