In this morning training, our team was given this problem from Prologin contest — 2015 Regional event (unfortunately, the statement is written in French, but I'll try to summarize the statement as accurate as possible):

"There are *N* rooms and *M* roads, road *i* directly connect room *u*_{i} with room *v*_{i}. There are also *K* switches, switch *i* can control road *a*_{i} and road *b*_{i}. More specifically, if switch *i* is on, roads *a*_{i} is enabled and roads *b*_{i} is disabled, and vice-versa (disabled road can't be walked on). If there is no switch controlling road *i*, then that road is always enabled. It's guaranteed that one road will be controlled by at most one switch, and when all switches are off, the roads system will form a tree (connected acyclic graph). Is it true that for all 2^{k} states of the switches, the roads system will always form a tree?"

Our teams have discussed this problem for the entire morning but failed to come up with any algorithm that can solve this problem in polynomial time. It also doesn't help that the original statement didn't give constraint of *N*, *M*, and *K*, too. Can someone help us on this matter? Thanks in advance.

Let's assume that the graph is colored. Roads

a_{i}andb_{i}are colored with colori, and the remainingM- 2Kedges are colored with black. Repeat the following while possible:After these process, we get a simple graph. If we end up with a single vertex, the answer is "YES". My hypothesis is that otherwise, the answer is "NO" — however I don't have a proof. I worked on some examples on paper but it looked hard to find counter-examples.

If my solution below is correct, we can prove that your is correct as well. After the contraction process we will get a simple graph without black edges. This means that every base cycle has length at least three, implying that the out-degree of every vertex in the graph

G(constructed like described in my comment below) is at least one there is a cycle and the answer isNO.Basically, you reduced problem to case when

m= 2k,n=k+ 1 (graph has no black edges). Then every cut in graph should include both edges of at least one color (otherwise we can assign switches in such way that no edges in cut will be enabled and graph of enabled edges will be disconnected). Ifn≥ 2 partition "any vertex" — "all remaining vertices" is a valid cut, so every vertex should be end of both edges of some color. In simple graph only one vertex can have this property for any color, so onlyk(number of colors) vertices fromn=k+ 1 can have such a property. Contradiction.If we assume the graph is colored (just like rng_58 described above), then the problem basically asks to check whether there exist a cycle containing no two edges of the same color.

The cycle space of a graph is a vector space. If we take a tree formed by all black edges and all

a_{i}and then for everyb_{i}take a cycle formed by this edge and the path between its endpoints from the tree (we will say that this cycle belongs to colorias well), such set ofkcycles will be a basis of the graphs cycle space.Note:We assume that the base cycle of coloricontains the edgea_{i}as well (otherwise we get a cyclic graph by toggling only switchi).Every cycle can be expressed as

xorof some base cycles. Let's assume the cycle we are looking for is anxorof base cycles with colorsc_{1},c_{2}, ...,c_{x}. All colors that are not amongc_{j}will have at most one edge in such cycle (because the only base cycle containingb_{i}has colori, so if we don't take this base cycle the only edge of coloriwe can potentially have isa_{i}). For each colorc_{j}our cycle will definitely have edgeb_{cj}, so we should make sure it doesn't containa_{cj}.Now let's construct another (directed) graph

Gwhere we have a vertex for every colorc_{j}and there is an edge from vertexutoviffa_{v}belongs to the base cycle of coloru(for simplicity let's say that self-loops are not included). Now the condition that our good cycle doesn't containa_{cj}is equivalent to "the in-degree of vertexc_{j}in the graphGis odd", which implies that every vertex has at least one incoming edge and subsequently implies that graphGhas a cycle.So, if we construct the graph

Gfor allkcolors and there are no cycles, we can be sure the answer isYES. I claim that otherwise the answer isNO.Let's prove the last claim. Take an arbitrary cycle from

G. If there are no other edges between the vertices of chosen cycle, then we are done. Otherwise, take arbitrary such edge, it divides the cycle into two parts where one of them form another (smaller) cycle. Now we replace our chosen cycle with the smaller one and continue until we eventually get a cycle with no other edges inside.