patternModerate
Algorithmic Complexity of Recognizing Claw-Free Graphs
Viewed 0 times
freegraphsclawrecognizingalgorithmiccomplexity
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#162703, answer score: 12
Revisions (0)
No revisions yet.