Favorable graph decomposition for dense graphs to solve independent set problem

Question

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?

Answer 1

The problem is that most decompositions (I know of) are themselves much harder to compute/approximate than INDEPENDENT SET.

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).

Answer 2

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.

Tree-length (see, for example, Tree-decompositions with bags of small diameter by Dourisboure and Gavoille), where the length of a tree decomposition is not the number of vertices in a biggest bag but the maximum distance between pairs of vertices of a bag, might be a more appropriate measure in such cases. While chordal graphs have unbounded treewidth, they have tree-length 1.