<p>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$.</p>

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

<p>If $\alpha=k/h$, we claim that $V_0'=T$. Assume not, then $|V_0'|&lt;k$. 
$|V_0'|+|V_1'|\geq k+h$, so $|V_1'|&gt; h$. But then $|V_0'|/|V_1'|&lt;\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. </p>

CC BY-SA 3.0
2016-07-15T04:11:09.377Z
2016-07-15T04:11:09.377Z
Chao Xu
<p>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.</p>

<p>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$ (<strong>fixed</strong>, 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.</p>

<p>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$.</p>

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

<p><a href="https://i.sstatic.net/EPju3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/EPju3.png" alt="Example with an optimal solution"></a></p>

<p>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?</p>

CC BY-SA 3.0
2016-07-14T19:10:41.123Z
1. Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.
D.W.
CC BY-SA 3.0
2016-07-15T11:26:27.783Z
I removed the original question on CS.SE.
clarabella
<graph-theory><graph-algorithms><optimization>
Maximum cardinality subgraphs meeting a Jaccard overlap threshold
clarabella
# Maximum cardinality subgraphs meeting a Jaccard overlap threshold

(Asked by: username_0 on 2016-07-14)

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](https://i.sstatic.net/EPju3.png)](https://i.sstatic.net/EPju3.png)

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?

**Tags:** graph-theory, graph-algorithms, optimization
> **Comments:**
> **username_1**: 1. Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). 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.  
> **username_0**: I removed the original question on CS.SE.  

---

## 1 answers

### Answer by username_2 on 2016-07-15. Score: 1

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'| 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.


---

