The clique problem on inductive $k$-independent graphs

Abstract

A graph is inductive $k$-independent if there exists and ordering of its vertices $v_1,...,v_n$ such that $\alpha (G[N(v_i)\cap V_i])\le k$ where $N(v_i)$ is the neighborhood of $v_i$, $V_i=\{v_i,...,v_n\}$ and $\alpha$ is the independence number. In this article, by answering to a question of [Y.Ye, A.Borodin, Elimination graphs, ACM Trans. Algorithms 8 (2) (2012) 14:1-14:23], we design a polynomial time approximation algorithm with ratio {$\overlineΔ \slash log(log(\overline{ Δ}) \slash k)$ for the maximum clique and also show that the decision version of this problem is fixed parameter tractable for this particular family of graphs with complexity $O(1.2127^{(p+k-1{)}^k}n)$. Then we study a subclass of inductive $k$-independent graphs, namely $k$-degenerate graphs. A graph is $k$-degenerate if there exists an ordering of its vertices $v_1,...,v_n$ such that $|N(v_i)\cap V_i|\le k$. Our contribution is an algorithm computing a maximum clique for this class of graphs in time $O(1.2127^k(n-k+1))$, thus improving previous best results. We also prove some structural properties for inductive $k$-independent graphs.

arXiv commentIt has been merged with another paper

References in corpus (1)

• An O(m) Algorithm for Cores Decomposition of Networks