Return to Answer

If you do not care about connectedness, then a necessary and sufficient condition is given by the matroid intersection theorem. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow forest exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total forest (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total forest exists. To see this, observe that if $T$ is the set of edges of a total forest, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.

If you do not care about connectedness, then a necessary and sufficient condition is given by the matroid intersection theorem. Let $G=(V,E)$ be a (not necessarily properly) edge-colored graph. Define a total forest to be the set of edges of a forest which contains every colour exactly once.

Let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow forest exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total forest (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total forest exists. To see this, observe that if $T$ is the set of edges of a total forest, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.

A necessary and sufficient condition is given by the matroid intersection theorem. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow tree exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total spanning tree (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total spanning tree exists. To see this, observe that if $T$ is the set of edges of a total spanning tree, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.

If you do not care about connectedness, then a necessary and sufficient condition is given by the matroid intersection theorem. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow forest exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total forest (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total forest exists. To see this, observe that if $T$ is the set of edges of a total forest, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.

A necessary and sufficient condition is given by the matroid intersection theorem. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow tree exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, note that $r_1$ and $r_2$ can be specified by oracles that run in polynomial time. Therefore, by running the matroid intersection algorithm, we can find a total spanning tree (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total spanning tree exists. To see this, observe that if $T$ is the set of edges of a total spanning tree, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.

A necessary and sufficient condition is given by the matroid intersection theorem. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, let $M_1$ be the matroid with ground set $E$, where a set is independent if and only if it contains at most one edge of each colour. Let $M_2$ be the matroid with ground set $E$ where a set is independent if and only if it does not contain a cycle. Let $r_1$ and $r_2$ be the rank functions of $M_1$ and $M_2$, and let $t$ be the total number of colours. Observe that a total rainbow tree exists if and only if $M_1$ and $M_2$ have a common independent set of size $t$. By the matroid intersection theorem this is true if and only if for all $A \subseteq E$,

$r_1(A) + r_2(E \setminus A) \geq t$.

Moreover, it is clear that independence testing for $M_1$ and $M_2$ can both be done in polynomial-time. Therefore, by running the matroid intersection algorithm, we can find a total spanning tree (if it exists) in polynomial-time, or a set $A \subseteq E$ such that

$r_1(A) + r_2(E \setminus A) < t$.

Note that such a set $A$ certifies that no total spanning tree exists. To see this, observe that if $T$ is the set of edges of a total spanning tree, then

$t=|T|=|T \cap A| +|T \cap (E \setminus A)| \leq r_1(A)+r_2(E \setminus A) < t$,

which is a contradiction.