Algorithmic Complexity of Recognizing Claw-Free Graphs

Question

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?

Answer 1

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.

Answer 2

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.