An $\mathcal{O}(n\sqrt{m})$ algorithm for the weighted stable set problem in {claw, net}-free graphs with $\alpha (G)\ge 4$

Abstract

In this paper we show that a connected {claw, net}-free graph $G(V,E)$ with $\alpha (G)\ge 4$ is the union of a strongly bisimplicial clique $Q$ and at most two clique-strips. A clique is strongly bisimplicial if its neighborhood is partitioned into two cliques which are mutually non-adjacent and a clique-strip is a sequence of cliques $\{H_0,\dots ,H_p\}$ with the property that $H_i$ is adjacent only to $H_{i-1}$ and $H_{i+1}$. By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem in such a graph in time $\mathcal{O}(|V|\sqrt{|E|})$.