21
$\begingroup$

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").
$\endgroup$
9
  • $\begingroup$ You can use Alon et al.'s method of finding triangle in $O(|E|^{1.41})$, for each node which end up at a $O(|V|\cdot |E|^{1.41})$ which is better than $|V|^{\omega+1}$ if the graph is not too dense. $\endgroup$
    – R B
    Apr 30, 2014 at 15:29
  • $\begingroup$ @RB, thank you for pointing this out. The basic idea is still to run the whatever-triangle-detection-algorithm $n$ times, which is what I want to avoid. $\endgroup$
    – Yixin Cao
    Apr 30, 2014 at 15:43
  • $\begingroup$ How can we expect to find some algorithm which is not related to triangle finding? Because whatever the algorithm is should check neighbors of each vertex. I mean that property is very local property, except with constant factor difference every vertex should be seen. (Or I cannot imagine any natural algorithm which avoids this locality). Do you have any even vague idea? $\endgroup$
    – Saeed
    Apr 30, 2014 at 16:39
  • 2
    $\begingroup$ Maybe it is good to mention that if we can find a claw in f(n) time, we can also find a triangle in f(n+1) time (just take the complement of the graph and add one more vertex connected to everyone), so we should not hope to find anything better than $n^\omega$. $\endgroup$
    – domotorp
    Apr 30, 2014 at 18:11
  • 1
    $\begingroup$ @domotorp, seems that part is clear, the other way around is not clear, I mean why we need linear search. As Yixin also pointed out, may be there is another algorithm which does not use a triangle finding algorithm and solves problem in $o(n^{\omega +1})$, which I think is hard to find such an algorithm and probably is easier to show that any algorithm uses triangle finding as subroutine (or can be converted) with linear search on it. $\endgroup$
    – Saeed
    Apr 30, 2014 at 19:01

2 Answers 2

16
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Great! This is exactly what I want for my first question: only one call of matrix multiplication, though a bigger one. I'll wait for more comments or answers on my second question before taking it as an answer. $\endgroup$
    – Yixin Cao
    May 1, 2014 at 13:33
15
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Wow, that's a clever idea, I was thinking whether is possible to do sublinear search (actually disproving this) and didn't even think about the intrinsic properties of the problem. $\endgroup$
    – Saeed
    Apr 30, 2014 at 20:44
  • $\begingroup$ Thank you David. I leave it open for a moment as my second question seems to be not noticed yet. $\endgroup$
    – Yixin Cao
    Apr 30, 2014 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.