Maximum cardinality subgraphs meeting a Jaccard overlap threshold

Question

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):

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?

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