8
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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})$. $\endgroup$
    – Tassle
    Nov 1, 2023 at 8:53
  • $\begingroup$ This definition differs from the one in wikipedia. Are you sure $f$ does not need to be a bijection? $\endgroup$
    – chi
    Nov 2, 2023 at 9:10
  • $\begingroup$ @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. $\endgroup$
    – licheng
    Nov 2, 2023 at 10:53

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Nov 2, 2023 at 3:28
  • $\begingroup$ Note the “random-ized technique‘’. $\endgroup$
    – licheng
    Nov 2, 2023 at 3:36
7
$\begingroup$

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.

$\endgroup$

Your Answer

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

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