Is it necessary to call matrix multiplication $n$ times to find a claw

Question

A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the subgraph induced by $N[v]$ for each vertex $v$, and find a triangle in its complement.

As far as I know, these basic algorithms are only known. Spinrad listed in his book "efficient graph representations" the detection of a claw in $o(n^{\omega+1})$ time as an open problem (8.3, page 103). For the lower bound, we know that an $O(n^c)$-time algorithm will imply an $O(n^{\max{(c,2)}})$-time algorithm for finding a triangle. So we may consider $\Omega(n^\omega)$ as a lower bound.

Question:

1. Is there any progress on this. Or any progress on showing it's impossible?
2. Are there other natural problems with $O(n^{\omega+1})$-time algorithms which are the best?

Remark:

1. I'm explicitly asking for the detection of a claw, instead of the recognition of claw-free graphs. Although an algorithm usually solves both, there are few exceptions.
2. It's claimed in Handbook of Algorithms and Theoretical Computer Science that it can be found in linear time, but it was only a typo (see "efficient graph representations").

Answer 1

I think that we can do slightly better than $O(n^{1+\omega})$ for dense graphs, by using rectangular matrix multiplication. A similar idea was used by Eisenbrand and Grandoni ("On the complexity of fixed parameter clique and dominating set", Theoretical Computer Science Volume 326(2004) 57–67) for 4-clique detection.

Let $G=(V,E)$ be the graph in which we want to detect the existence of a claw. Let $A$ be the set of (ordered) pairs of vertices in $V$. Consider the following Boolean matrix $M$ of size $|V|\times |A|$: each row is indexed by some $u\in V$, each column is indexed by some $(v,w)\in A$, and the corresponding entry is one if and only if $\{u,v\}\in E$, $\{v,w\}\in E$ and $\{u,w\}\notin E$. Consider the Boolean matrix product of $M$ and its transpose $M^T$. The graph $G$ has a claw if and only if there exists $\{u,v\}\notin E$ such that the entry of $MM^T$ in the row indexed by $u$ and the column indexed by $v$ is one.

The complexity of this algorithm is essentially the complexity of computing the Boolean product of an $n\times n^2$ matrix by a $n^2\times n$ matrix, where $n$ denotes the number of vertices in the graph. It is known that such a matrix product can be computed in time $O(n^{3.3})$, which is better than $O(n^{1+\omega})$ for the best known upper bound on $\omega$. Of course, if $\omega=2$ (as conjectured) then the two approaches give the same complexity $O(n^3)$.

Answer 2

I don't know how to avoid doing $n$ matrix multiplies, but you can analyze it in such a way that the time is effectively that of a smaller number of them. This trick is from

Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), "Finding and counting small induced subgraphs efficiently", Information Processing Letters 74 (3–4): 115–121, doi:10.1016/S0020-0190(00)00047-8, MR 1761552.

The first observation is that, when you're going matrix multiplies, the matrices are not really $n\times n$, but $d\times d$ where $d$ is the degree of each vertex, because what you're looking for is a co-triangle in the neighborhood of each vertex.

Second, in a claw-free graph, every vertex must have $O(\sqrt m)$ neighbors. For, otherwise the set of neighbors would have too few edges to avoid having a triangle in the complement. So when you're doing matrix multiplications, you only need to do it on matrices of size $O(\sqrt m)$ rather than $n$.

In addition, each edge can contribute to the size of the matrix multiplication problem for only two vertices, its endpoints. The worst case happens when the $2m$ for the total size of these matrix multiplication problems is spread into $O(\sqrt m)$ subproblems of size $O(\sqrt m)$ each, which gives a total time bound of $O(m^{(1+\omega)/2})$, an improvement for sparse graphs over the $O(nm^{\omega/2})$ bound mentioned by R B.