# Favorable graph decomposition for dense graphs to solve independent set problem

I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or clique-width k-expression trees.

Are there some decompositions (or other techniques) favorable for my type of graphs?

From what I understand, considering e.g. the tree-decomposition, the ISP can be solved in $\mathcal{O}(n2^k)$ where $n$ is number of vertices of the tree and $k$ the tree-width. Moreover, the tree-width is a measure of how similar a graph is to a tree. From this, I concluded that a graph which is not very similar to tree (maybe just like mine) has a large tree-width and, hence, the tree-decomposition is maybe not a favorable decomposition to solve the ISP.

Is e.g. the clique-width k-expression tree more suitable for my case?

• Independent set problem is P in graphs of bounded clique width but not every dense graph is bounded clique width. Commented Aug 27, 2015 at 20:44
• when you say "Trying to solve" do you mean code that works well on a particular data set, or do you have a theory application in mind? Commented Sep 2, 2015 at 8:04
• @daniello, I'm mainly interested in solving these problem efficiently. Commented Sep 10, 2015 at 19:21

However, if your graphs are really very dense, their complements might be sparse. Thus, it might be worth considering solving CLIQUE in the complement of the input graph. This can be done in $O(nd\cdot 1.45^d)$ time (Eppstein, Löffler, Strash), where $d$ is the degeneracy of the input graph (which is even smaller than the treewidth).
Large treewidth does not directly mean that the usual dynamic programming algorithm for independent set will perform poorly. While the biggest table could have $2^{w + 1}$ entries when given a tree decomposition of width $w$, this case will only occur if the bag itself is an independent set. The number of entries in a table directly corresponds to the number of independent sets of the graph induced by the vertices of the associated bag. Hence, if these subgraphs do not have many independent sets, you can probably expect good performance in practice.
For example, independent set can be solved in polynomial time on chordal graphs by constructing a clique tree (basically a tree decomposition where every bag is a clique), and then running the dynamic programming algorithm for treewidth on it. A bag of size $k$ has only $k + 1$ entries, because at most one vertex from a clique can be part of an independet set, and also an entry for the "empty" independent set is kept.