Algorithmic Complexity of Recognizing Claw-Free Graphs

Let $$H=\left(V_H, E_H\right)$$ and $$G=(V, E)$$ be graphs. A subgraph isomorphism from $$H$$ to $$G$$ is a function $$f: V_H \rightarrow V$$ such that if $$(u, v) \in E_H$$, then $$(f(u), f(v)) \in E$$. $$f$$ is an induced subgraph isomorphism if in addition if $$(u, v) \notin E_H$$, then $$(f(u), f(v)) \notin E$$.

A claw is another name for the complete bipartite graph $$K_{1,3}$$. A claw-free graph is a graph that does not have a claw as an induced subgraph.

I know, in general, that induced subgraph isomorphism is an NP-complete problem. However, the situation may be different for certain special induced-subgraphs. For example, $$C_3$$.

Claw-free graphs were initially studied as a generalization of line graphs （the line graph $$L(G)$$ of any graph $$G$$ is claw-free), and Roussopoulos (1973) and Lehot (1974) described linear time algorithms for recognizing line graphs and reconstructing their original graphs.

Our question is, what is the algorithmic complexity of identifying whether a graph contains an induced claw? Are they polynomial, or even linear?

• Have you tried Wikipedia? It mentions a $O(n^{3.376})$ algorithm and a $O(m^{1.688})$ algorithm. If matrix multiplication turns out to be quadratic time, I think these runtimes would reduce to $\tilde{O}(n^{3})$ and $\tilde{O}(m^{3/2})$. Commented Nov 1, 2023 at 8:53
• This definition differs from the one in wikipedia. Are you sure $f$ does not need to be a bijection?
– chi
Commented Nov 2, 2023 at 9:10
• @chi The meaning of $f$ on Wikipedia is a bit different from what it means here. I believe they are referring to the same thing. Commented Nov 2, 2023 at 10:53

A graph is, as you say, claw-free if and only if it does not contain $$K_{1,3}$$ as an induced subgraph.

This gives rise to the trivial $$n^4$$ algorithm: for every set of four vertices, is the degrees of the induced subgraph $$3,1,1,1$$?

Steven, in another thread, points to a paper by Williams, Wang, Williams, and Yu that give an algorithm for claw detection running in matrix-multiplication time $$O(n^\omega)$$, where $$\omega < 2.3728$$.

Williams, Wang, Williams, and Yu, Finding Four-Node Subgraphs in Triangle Time, SODA 2015.

• The authors in “Finding Four-Node Subgraphs in Triangle Time” said they give a general random-ized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes. I'm a bit worried whether this algorithm will definitely succeed. Commented Nov 2, 2023 at 3:28
• Note the “random-ized technique‘’. Commented Nov 2, 2023 at 3:36

Let $$G$$ be our graph. For each vertex $$v \in V(G)$$, let $$H_v$$ be the complement of the subgraph consisting of all vertices adjacent to $$v$$. We find an induced $$K_{1,3}$$ in $$G$$ if and only if there is any vertex $$v$$ for which $$H_v$$ contains a triangle.

Of course, there is the trivial $$O(n^3)$$ algorithm for testing if $$H_v$$ contains a triangle, for an overall $$O(n^4)$$ algorithm for the original problem. But we can do better for large graphs: if $$A_v$$ is the adjacency matrix of $$H_v$$, then $$H_v$$ contains a triangle if and only if $$(A_v)^3$$ has any nonzero diagonal entries. This gets our complexity down to $$O(n^{\omega+1})$$, where $$\omega$$ is the exponent for fast matrix multiplication.

Let $$m$$ be the number of edges in $$G$$. There's also an $$O(n^2m)$$ algorithm useful for sparse graphs (and related to the $$O(nm)$$ algorithm for triangles). Looping over every edge $$xy$$ and every non-adjacent pair $$\{u,v\}$$, check whether one of $$x,y$$ is adjacent to both $$u$$ and $$v$$ and the other is adjacent to neither. This happens exactly when $$x,y,u,v$$ induce a $$K_{1,3}$$.

With a little bit more care, we can make this $$O(m^2)$$ (where I am assuming $$m \ge n$$). Instead of the above, for every edge $$xy$$:

1. Go through all the edges $$uv$$ and find how many satisfy the same condition: $$u$$ and $$v$$ are both adjacent to $$x$$ but not $$y$$, or vice versa. This counts the paw graphs in which $$xy$$ is the non-cycle edge.
2. Going through all the vertices other than $$x$$ and $$y$$, let $$n_x$$ be the number adjacent to $$x$$ but not $$y$$, and let $$n_y$$ be the number adjacent to $$y$$ but not $$x$$. Then $$\binom{n_x}{2} + \binom{n_y}{2}$$ counts the number of both claws containing $$xy$$ and paws in which $$xy$$ is the non-cycle edge.

Subtracting, we determine whether $$xy$$ is part of any claw.

As a lower bound, we can't beat the complexity of triangle-finding, because for any graph $$H$$, we can construct $$G$$ by taking the complement and adding a new vertex adjacent to all vertices of the resulting graph. Then, $$H$$ is triangle-free if and only if $$G$$ is claw-free.