Given an undirected graph $G=(V,E,p,c)$ and a positive integer $k$, $p: V \longrightarrow R^+$ which associates a positive weights $p(v_i)$ to every node $v_i \in V$, and $c: E \longrightarrow R^+$ which associates a positive cost $c(e_{i,j})$ to every edge $e_{ij} \in E$. How can I find a subgraph $G'=(V_{G'},E_{G'})$, $V_{G'}\subseteq V$, under constraint $ \forall v_i,v_j \in V_{G'}$ , $e_{i,j} \in E_{G'}$ with the minimum number of vertices such that:

\begin{equation} \sum_{v \in V_{G'}} p(v)-\sum_{e \in E_{G'}}c(e) \geq k \end{equation}

I think this problem is NP-hard (because it is an optimization problem), as there is a reduction from k-clique, is it true? if yes, there is an approximate algorithm to find a near optimal solution? I try to solve this problem using ILP integer linear programming on cplex :

$min \sum_{v_i \in V} v_i$

subject to :

$\sum_{v_i=1} p(v)-\sum_{i\ne j,v_i=v_j=1 }c(e_{i,j}) \geq k$

$v_i,v_j \in \{0,1\}$

, but this solution is not useful when it comes to a very large graph .

Context of the problem :

Given a collection of $n$ sets $S=\{S_1,...,S_n\}$ and a integer $k$ how to find the minimum number of sets $m$ whose size of their union is greater than $k$ $ |\bigcup_{i=1}^{m} S_i|≥k$ . I model this problem in the form of a graph where the $S$ represents the set of vertices, $p(v_i)=|S_i|$ and $c(e_{i,j})=|S_i \cap S_j|$ . So i obtain the problem described above.

For example,

enter image description here

if $k=12$ the solution is G'with $V_{G'}=\{v_2,v_5,v_6\}$ and $E_{G'}=\{e_{5,6}\}$.

  • 1
    $\begingroup$ I still don't see any statement in the question that the all edges between selected vertices must be selected... $\endgroup$ – D.W. Apr 16 '18 at 1:13
  • $\begingroup$ you can look at the context of the problem to understand why all edges between selected vertices must be selected . $\endgroup$ – atef Apr 16 '18 at 8:23
  • $\begingroup$ @ j_random_hacker thank you for this clarification, I update my question $\endgroup$ – atef Apr 16 '18 at 9:16
  • 1
    $\begingroup$ Thanks for fixing your question. Unfortunately this problem is NP-hard: You could solve Clique by changing every edge to a non-edge, and every non-edge to an edge with very high weight, setting $p(v_i)=1$ for all $i$ and then setting $k$ to the size of the clique you want. The only induced subgraphs of the new graph with weight $\ge k$ contain no edges and at least $k$ vertices, i.e. they are independent sets of size $\ge k$, corresponding to cliques of size $\ge k$ in the original graph. $\endgroup$ – j_random_hacker Apr 16 '18 at 10:40
  • 1
    $\begingroup$ It seems you make the problem complicated. This paper seems to solve your primary problem. BTW, you primary problem is NP-hard because it is exactly the set cover problem if $k=\left|\bigcup_{i=1}^nS_i\right|$. $\endgroup$ – xskxzr Apr 16 '18 at 11:22

Your Answer

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

Browse other questions tagged or ask your own question.