3

EDIT: The answers below are for previous versions of the question. Answer for third version: [This version asked for an edge-colored graph $G$ with a vertex $r$ such that has exactly three edges $a,b,c$, with colors $1,2,3$, and such that $G$ has at least two properly colored spanning trees $T_1$ and $T_2$ such that $T_1$ has $a$ and not $b$ or $c$, and $T_2$...


3

As written, the problem is NP-complete even when you require the elements of $S$ to be pairwise disjoint (which also implies that every vertex belongs to a unique element of $S$): as a reduction from $q$-COLOURABILITY, we can attach to each vertex $q-1$ new vertices to form a $q$-clique. This does not contradict the results from the cited paper by Klotz, ...


2

Just a partial answer. Gallai's conjecture was recently proven for planar graphs: https://arxiv.org/abs/2110.08870. The paper gives an algorithm to find the $\lceil \frac{n}{2}\rceil$ desired paths. It is "polynomial" (it uses a "black-box" for finding $K_5$ subdivisions, I don't know if it can be done polynomially). However, I think that ...


2

I still do not have any ideas about the general answer to this question, but I think I have an argument against the possibility to construct such a circuit in so-called monotone "decomposable negation normal form" or monotone DNNF. This is a circuit with no negations where, for every AND-gate, the inputs do not "depend" on any common ...


Only top voted, non community-wiki answers of a minimum length are eligible