Is there an efficient algorithm to count how many ways there are to decompose a given finite simple undirected connected graph $G = (V, E)$ into the union of two trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ that are not necessarily edge-disjoint? By union I mean $V = V_1 \cup V_2$ and $E = E_1 \cup E_2$. My initial thoughts:

  1. $V_1$ and $V_2$ cannot be disjoint, so $|V_1| + |V_2| > |V|$.
  2. $|V_1| + |V_2| \geq |E| + 2$ because $E_1 \cup E_2 = E$ and $|E_i| = |V_i| - 1$.
  3. If $G$ is a tree then we are counting the number of ways to write $V = V_1\cup V_2$ where $V_1$ and $V_2$ are not disjoint. This can be presumably calculated analytically.
  • $\begingroup$ 3. It's not that simple. Consider tree $1-2-3$: you can't split it as $(1,3)$ and $(2)$. While you do can compute the answer for the case when $G$ is a tree, it's by no means trivial. Currently, I'm not sure it's possible to do this for general graphs efficiently. We can use property 2 (it must hold $2|V| \ge |E| + 2$ for any subgraph) to say that the answer is 0 in some cases. $\endgroup$ – Dmitry Aug 5 '20 at 13:08
  • $\begingroup$ Your example comprises disjoint vertex sets. $\endgroup$ – abhi01nat Aug 5 '20 at 13:14
  • $\begingroup$ $1-2-3-4-5$ split as $(1,2,4,5)$ and $(2,3,4)$ $\endgroup$ – Dmitry Aug 5 '20 at 13:28
  • $\begingroup$ Ah ok understood, thanks! $\endgroup$ – abhi01nat Aug 5 '20 at 13:32
  • $\begingroup$ @abhi01nat property 1 isn't actually true right? Shouldn't it be $|V_1|+|V_2| > |V|$? Both trees don't have to contain more than half of the nodes only one of them has to. (I'm criticizing the phrase "so each"). $\endgroup$ – plshelp Aug 11 '20 at 13:43

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.