PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:HARD PREREQUISITES:Graphs PROBLEM:You are given a graph and you have to decide if it is a halved cube graph which is a subgraph of hypercube graph formed by connecting pairs of verices at distance exactly two from each other in the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph. CHARACTERIZATIONLet Qd be a hypercube of order d and let Hd be a halved cube of order d. Let's consider a hypercube graph Qd first. Qd has n = 2^d vertices and there is a very handful way of defining it. Let vertices of Qd be the set of all binary strings of length d. We connect two vertices if and only if their corresponding binary strings differ by exactly one bit. Based on this definition, it is easy to see that Qd is a dregular graph with 2^d1 * d edges and diameter d. Let's consier a vertex v of Qd. In order to know how to form a halved cube, we want to know how many vertices are at distance exactly two from v. Our handful definition shows that there are binomial(d, 2) vertices at distance two from v, because there are binomial(d, 2) binary strings different on exactly two bits from the string assigned to v. You can try to construct one such graph it by hand. For example H3 is a complete graph over 4 vertices. QUICK EXPLANATION:You can implement the algorithm described in this paper. EXPLANATION:All fact below are based on the paper. I don't give here a complete solution, because it is well presented in the paper. You can assume that d >= 5, because we can recognize every Hd for d < 5 which is really easy. It is known than Hd has 2^(d1) cliques of size d. Here is a sketch of the algorithm: The algorithm works in steps: Input: graph G on n vertices
Paper describes every step with all details. In order to understand the logic behind the construction in step 2 let's consider any clique C. If G is a halved cube graph, then all pairs of vertices in C are at distance 2 in the corresponding hypercube graph. Based on this fact, it is easy to see that in there must be a vertex u in Qn such that u is as distance 1 from any of vertices in C. Please check the paper for more details. AUTHOR'S AND TESTER'S SOLUTIONS:To be uploaded soon. RELATED PROBLEMS:To be uploaded soon.
This question is marked "community wiki".
asked 16 Dec '14, 06:16

I'm the author of this problem. I noticed the fact that wrong solutions passed with checking just 2(d2) property during the contest. I tried to generate tests against these solutions. I used bruteforce with some heuristics to find graphs with necessary dregularity property and this 2(d2) property. Bruteforce found ~30 000 graphs with N=16 and all of them were halvedcubed graphs. Unfortunately it wasn't enough fast to find at least one graph with these properties where N=32. So I didn't managed to generate tests against this simple heuristic and still have no idea what is the smallest value of N where a contrtest can be found. So it would be nice if someone had ideas how to find a contrtest against this heuristic and shared with us. answered 16 Dec '14, 15:41

I also used the fact of the binary strings :) Original graph:
Graph after passing commet (good galaxy):
Algorithm:
Although it's sure, the graph is a good galaxy if all numbers are getting assigned. The opposite is not true. Due to the original sequence, we may assign the wrong number at some stage. And this may give incorrect, while it is a good galaxy. I solved this by just trying 2 different sequences and this worked for me. I'm sorry that this is not fully correct, but I thought that was the trick. As long as the probability of passing is high enough. answered 16 Dec '14, 15:57

I found the paper mentioned about an hour from the point when I read the question, got AC after 7 days. In retrospect, I should have figured out the mistake waaaaaay earlier. The given test input has got an empty line between each case which I was taking in accordingly, but it is not there in the hidden test cases, so I was essentially ignoring one line of input. An extra empty line doesn't matter in C, C++. It does in Python. : By the time I figured out the problem, I didn't have much time to form the whole solution, tried just the 2*(d  2) constraint and it worked. :D I also tried the bit assignment approach. Assigned dbit numbers to all nodes such that the hamming distance between adjacent nodes should be 2. Unfortunately, that was while I was taking input incorrectly so I am still not sure if that approach would have worked, gonna have to try that out later. answered 16 Dec '14, 16:23

I think most people (including me!) were lucky to get away with just checking if the graph was ( (d choose 2), 2^(d1) )regular and checking that the size of intersection of the neighborhood's of every pairs of points was 2*(d2). But awesome question, and well written up as well :) answered 16 Dec '14, 11:59

what i did was: answered 16 Dec '14, 16:37
