Median Graph - Triangle-free Graphs and Recognition Algorithms

Triangle-free Graphs and Recognition Algorithms

The problems of testing whether a graph is a median graph, and whether a graph is triangle-free, both had been well studied when Imrich, Klavžar & Mulder (1999) observed that, in some sense, they are computationally equivalent. Therefore, the best known time bound for testing whether a graph is triangle-free, O(m1.41), applies as well to testing whether a graph is a median graph, and any improvement in median graph testing algorithms would also lead to an improvement in algorithms for detecting triangles in graphs.

In one direction, suppose one is given as input a graph G, and must test whether G is triangle-free. From G, construct a new graph H having as vertices each set of zero, one, or two adjacent vertices of G. Two such sets are adjacent in H when they differ by exactly one vertex. An equivalent description of H is that it is formed by splitting each edge of G into a path of two edges, and adding a new vertex connected to all the original vertices of G. This graph H is by construction a partial cube, but it is a median graph only when G is triangle-free: if a, b, and c form a triangle in G, then {a,b}, {a,c}, and {b,c} have no median in H, for such a median would have to correspond to the set {a,b,c}, but sets of three or more vertices of G do not form vertices in H. Therefore, G is triangle-free if and only if H is a median graph. In the case that G is triangle-free, H is its simplex graph. An algorithm to test efficiently whether H is a median graph could by this construction also be used to test whether G is triangle-free. This transformation preserves the computational complexity of the problem, for the size of H is proportional to that of G.

The reduction in the other direction, from triangle detection to median graph testing, is more involved and depends on the previous median graph recognition algorithm of Hagauer, Imrich & Klavžar (1999), which tests several necessary conditions for median graphs in near-linear time. The key new step involves using a breadth first search to partition the graph into levels according to their distances from some arbitrarily chosen root vertex, forming a graph in each level in which two vertices are adjacent if they share a common neighbor in the previous level, and searching for triangles in these graphs. The median of any such triangle must be a common neighbor of the three triangle vertices; if this common neighbor does not exist, the graph is not a median graph. If all triangles found in this way have medians, and the previous algorithm finds that the graph satisfies all the other conditions for being a median graph, then it must actually be a median graph. Note that this algorithm requires, not just the ability to test whether a triangle exists, but a list of all triangles in the level graph. In arbitrary graphs, listing all triangles sometimes requires Ω(m3/2) time, as some graphs have that many triangles, however Hagauer et al. show that the number of triangles arising in the level graphs of their reduction is near-linear, allowing the Alon et al. fast matrix multiplication based technique for finding triangles to be used.