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?
Maximum cardinality subgraphs meeting a Jaccard overlap threshold
graph theory;graph algorithms;optimization