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:
- Is there any progress on this. Or any progress on showing it's impossible?
- Are there other natural problems with $O(n^{\omega+1})$-time algorithms which are the best?
Remark:
- 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.
- 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").