xuanquang1999's blog

Need help with another graph theory problem
By xuanquang1999, history, 7 years ago, In English

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 ui with room vi. There are also K switches, switch i can control road ai and road bi. More specifically, if switch i is on, roads ai is enabled and roads bi 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 2k 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.

  • Vote: I like it
  • +104
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Let's assume that the graph is colored. Roads ai and bi are colored with color i, and the remaining M - 2K edges are colored with black. Repeat the following while possible:

  • If there is a black edge, we can contract the graph with this edge.
  • If there are two edges of the same color that connect the same pair of vertices, we can contract the graph with these two edges.
  • If there are two edges of different colors that connect the same pair of vertices, the answer is "NO".
  • If the graph contains self-loops (this is possible after some contractions), the answer is "NO".

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 is NO.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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). If n ≥ 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 only k (number of colors) vertices from n = k + 1 can have such a property. Contradiction.

    → Reply
»
7 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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 ai and then for every bi take a cycle formed by this edge and the path between its endpoints from the tree (we will say that this cycle belongs to color i as well), such set of k cycles will be a basis of the graphs cycle space.

Note: We assume that the base cycle of color i contains the edge ai as well (otherwise we get a cyclic graph by toggling only switch i).

Every cycle can be expressed as xor of some base cycles. Let's assume the cycle we are looking for is an xor of base cycles with colors c1, c2, ..., cx. All colors that are not among cj will have at most one edge in such cycle (because the only base cycle containing bi has color i, so if we don't take this base cycle the only edge of color i we can potentially have is ai). For each color cj our cycle will definitely have edge bcj, so we should make sure it doesn't contain acj.

Now let's construct another (directed) graph G where we have a vertex for every color cj and there is an edge from vertex u to v iff av belongs to the base cycle of color u (for simplicity let's say that self-loops are not included). Now the condition that our good cycle doesn't contain acj is equivalent to "the in-degree of vertex cj in the graph G is odd", which implies that every vertex has at least one incoming edge and subsequently implies that graph G has a cycle.

So, if we construct the graph G for all k colors and there are no cycles, we can be sure the answer is YES. I claim that otherwise the answer is NO.

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.

→ Reply