PROBLEM LINK:Authors: Arjun Arul, Praveen Dhinwa DIFFICULTY:mediumhard PREREQUISITES:Graph theory, bipartite graph, interval graph PROBLEM:A graph is called far graph if you can find a positive even integer $L$, and you can assign distinct integers $a_i$ to its nodes such that there will be an edge between node $i$ and $j$ if and only if $a_i  a_j \geq \frac{L}{2}$. You are given a graph $G$, tell whether this graph is a possible far graph or not. If yes, output any possible assignment of $a_i$ values to the nodes. Solve a simplified versionLet us assume that the problem has the condition for an edge to be $ a_i  a_j  > \frac{L}{2}$ instead of $ a_i  a_j  \geq \frac{L}{2}$. Also note that for better understanding, we will output the values with the condition: $0 \leq a_i \leq L$. In the original problem, you will have to output values with condition $\frac{L}{2} \leq a_i \leq \frac{L}{2}$. Let us now take any valid assignment of values to the integers and analyze the structure of the induced far graph: Note that the set of points in $[0, \frac{L}{2}]$ and $(\frac{L}{2}, L]$ will form independent sets. In other words, there won't be edges between two numbers if they both lie in the range $[0, \frac{L}{2}]$, or in the range $(\frac{L}{2}, L]$. This is because there can't exist two elements in these ranges that can have their difference greater than the length of the respective range(i.e., $\frac{L}{2}$). Hence, you can see that the resulting graph will be a bipartite graph. Suppose $a_1 < a_2 < ... < a_n$. If we view the points $a_i$ in $[0, \frac{L}{2}]$ in ascending order, the neighborhoods would form a chain based on inclusion. Formally, let $i, j$ be two indices such that $i < j$ and $0 \leq a_i < a_j \leq \frac{L}{2}$. Then the neighbors of $i$ will be all the integers in the range $[k, n]$ such that $a_k  a_i > \frac{L}{2}$. The point to note is that, the neighbors of $j$ will be all integers in the range $[k', n]$ for some k' such that $k' \geq k$. Thus, the neighborhood of a point will be contained in the neighborhood of a point to its left. Similarly, for the points in the range $(\frac{L}{2}, L]$, a similar condition applies. It turns out that this is a necessary and sufficient condition. That is, the given graph should be bipartite, and in both the partitions, the neighborhood sets of all the vertices should form a chain based on inclusion. Why is this true? Due to above arguments, you can easily see that it's a necessary condition. As for proving sufficiency, you can greedily assign the coordinates, if these conditions are met (explained below). Thus we prove that this condition is also sufficient (ie. proof by construction). Also note that in a valid far graph, excluding the vertices with degree 0, there is a unique bipartition. Details of greedy assignment Finding the actual integers $a_i$ can be done after this. You can go in the set of vertices of $A$ from right to left and can assign the values to some elements of $B$ (from right to left). The ranges of values are up to $10^9$, so you can assign large enough values for $L$ and for array $a$. You might have to consider degree zero elements in your code carefully. Handle the original versionBut with $ a_i  a_j  \geq \frac{L}{2}$, the graph need not be bipartite as $0, \frac{L}{2}, L$ could form a 3cycle. Observe that if you remove this 3cycle, then the graph is bipartite. So this is the only obstruction. In this case, you do the same algorithm as above, but after fixing these 3 points. A few more additional conditions need to be checked too. For example, if the graph contains a 3cycle and there exists a vertex with zero degrees, then there can't exist a far graph for this situation and answer would be No. Suppose the 3cycle is between $a_1, a_i, a_n$, then the degree of $a_i$ should be exactly two. Checking whether a graph contains three cycles. In fact, for this problem, you can use direct bruteforce in $\mathcal{O}(n^3/6)$ operations. This will also pass within time. There is an interesting and faster solution to find the 3cycle using the structure of the far graph. Note that only $a_1, a_i, a_n$ can form a 3cycle for some single $i$. One of the nodes $a_1, a_n$ should have the maximal degree in the entire graph. Wlog assume it is $a_1$. The node $a_n$ will be the neighbor of $a_1$ with the maximal degree. This way you will have fixed two of the endpoints of the 3cycle, now iterate over all other $n2$ vertices and check whether $a_1, a_n$ and that vertex form a cycle or not. The simplified version is called Difference Graphs in literature, and you can read more about them here. SOLUTIONS
This question is marked "community wiki".
asked 21 Jan '18, 18:13

Answer is hidden as author is suspended. Click here to view.
answered 22 Jan '18, 16:59
