Testing triangle-freeness

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!). This simple algorithm is the best known !! In other words, following is the open problem :

• Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?
  

A recent paper [1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?


[1] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.

Graceful Trees !!

I posted my favorite open problem (is every tree graceful ?) on the open problem garden. There are many more interesting open problems on this site.

Open Problem Garden !!

Let me point you to this great site on open problems in mathematics, graph theory and theoretical computer science.

• Open Problem Garden

I found this through Computational Complexity blog.

Graceful Tree Conjecture

Label the vertices of a simple undirected graph G(V,E) (where V = n and E = m) with integers from 0 to m. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled 1 through m inclusive (with no number repeated).

A graph is called graceful if it has atleast one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.

Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.

The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.

Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees have been shown to be graceful. These restriced classes include paths, stars, complete bi-partite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.