PROBLEM LINK:
Author: Gerald Agapov
Tester: Tasnim Imran Sunny
Editorialist: Jingbo Shang
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory, Line Graph
PROBLEM:
Given a line graph L corresponding to a graph G with at least one node whose degree is greater or equal to 4, try to reconstruct the original graph. Answers are guaranteed existed.
EXPLANATION:
Line graph (Denote as L(G)) is well studied before. Even if we considering any general graphs, as stated in wiki, linear time algorithms are already proposed by Roussopoulos (1973) and Lehot (1974) for bi-directed graph. Later, Sysło (1982) generalized these methods to directed graphs.
The basic idea of the algorithm is constructing the input line graph L by adding vertex one by one. Each time, we choose a vertex to add that is adjacent to at least one previously-added vertex. Meanwhile, let’s maintain a graph G for which L = L(G) (simply restore the “nodes” of added “edges”/“node in line graph”). If the algorithm ever fails to find an appropriate graph G, then the input is not a line graph and the algorithm terminates. (We don’t need to take care of such case, just put it here for some general purpose).
But, we found that this algorithm will meet some problems when adding a vertex v to a graph L(G) for which G has four or fewer vertices, it might be the case that the line graph representation is not unique (copied from wiki). Luckily, we have a great condition that we have a node with at least 4 edges in the original graph. Therefore, there exists a K4 in L. This provides us the chance to avoid the brute-force search in the beginning of the algorithm.
In summary, we can solve this problem in linear time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.