2
$\begingroup$

Consider two undirected connected graphs $G_0$ and $G_1$. The graphs are subgraphs of a given connected graph $G$ and share at least one node.

I want to find two subgraphs $G_0'\subseteq G_0$ and $G_1'\subseteq G_1$ such that they are connected, and the Jaccard index of their node sets is greater than a threshold $\alpha$ (fixed, between 0 and 1), that is $J=\frac{\left\vert V_0' \cap V_1'\right\vert }{\left\vert V_0' \cup V_1'\right\vert} \geq \alpha$ and these subgraphs are such that the sum $\left\vert V_0'\right\vert+ \left\vert V_1'\right\vert$ is maximized.

Starting from $G_0' = G_0,G_1' = G_1$, for the purpose of increasing $J$, while keeping connectedness of both graphs, I know I can unilaterally decrease the denominator of J by progressively removing as many nodes as possible that are in the nodes set difference $S=(V_0 \cup V_1) \setminus (V_0 \cap V_1)$, and are leaves of a spanning tree of $G_0'$ or $G_1'$. However it might be the case that no such leaf exists, yet I can obtain a higher overlap cutting bigger parts of possibly both graphs and renouncing to part of the intersection, yet having a lower $\left\vert V_0'+V_1'\right\vert$.

An example with an optimal solution (the intersection of the two subgraphs is highlighted in gray):

Example with an optimal solution

Can you think of an efficient algorithm that explores the subsets with some guarantee, maybe exploiting the upper bound $J \leq \frac{\min(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}{\max(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}$. Is this problem tractable?

$\endgroup$
  • $\begingroup$ 1. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. 2. You might want to update this copy of the question to incorporate the example you added on CS.SE. $\endgroup$ – D.W. Jul 14 '16 at 19:10
  • $\begingroup$ I removed the original question on CS.SE. $\endgroup$ – clarabella Jul 15 '16 at 11:26
1
$\begingroup$

The problem is NP-hard if $\alpha$ is part of the input. We can reduce the Steiner tree problem to this. Given a graph $G$ and terminal vertices $T$, consider $G_0$ to be a complete graph on $T$, and $G_1=G$.

Let $|T|=k$ and the size of the minimum Steiner tree of $T$ in $G$ be $h$.

If $\alpha=k/h$, we claim that $V_0'=T$. Assume not, then $|V_0'|<k$. $|V_0'|+|V_1'|\geq k+h$, so $|V_1'|> h$. But then $|V_0'|/|V_1'|<\alpha$. A contradiction. Also, $|V_1'|=h$, as anything larger violates $|V_0'|/|V_1'|\geq \alpha$. $V_1'$ also gives us the vertices of a minimum Steiner tree on $T$. We can obtain $h$ by guess every possible $h$, there are only $n$ possibilities. Hence we reduce Steiner tree problem to your problem.

$\endgroup$

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.