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

<p>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 (<a href="http://arxiv.org/pdf/1006.5440" rel="nofollow">Eppstein, Löffler, Strash</a>), where $d$ is the degeneracy of the input graph (which is even smaller than the treewidth).</p>

CC BY-SA 3.0
2015-10-22T08:15:22.960Z
2015-10-22T08:15:22.960Z
igel
<p>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.</p>

<p>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.</p>

<p><em>Tree-length</em> (see, for example, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.396.4536" rel="nofollow">Tree-decompositions with bags of small diameter</a> by Dourisboure and Gavoille), where the <em>length</em> 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.</p>

CC BY-SA 3.0
2015-10-25T22:28:15.003Z
2015-10-25T22:28:15.003Z
Tobi
<p>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 <a href="https://de.wikipedia.org/wiki/Cliquenweite" rel="nofollow">clique-width k-expression</a> trees. </p>

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

<p>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.</p>

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

CC BY-SA 3.0
2015-08-27T20:44:51.597Z
Independent set problem is P in graphs of bounded clique width but not every dense graph is bounded clique width.
Saeed
CC BY-SA 3.0
2015-09-02T08:04:23.243Z
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?
daniello
CC BY-SA 3.0
2015-09-10T19:21:46.327Z
@daniello, I'm mainly interested in solving these problem efficiently.
user35296
<graph-theory><graph-algorithms>
Favorable graph decomposition for dense graphs to solve independent set problem
user35296
# Favorable graph decomposition for dense graphs to solve independent set problem

(Asked by: username_0 on 2015-08-27)

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](https://de.wikipedia.org/wiki/Cliquenweite) 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?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Independent set problem is P in graphs of bounded clique width but not every dense graph is bounded clique width.  
> **username_2**: 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?  
> **username_0**: @daniello, I'm mainly interested in solving these problem efficiently.  

---

## 2 answers

### Answer by username_3 on 2015-10-22. Score: 4

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](http://arxiv.org/pdf/1006.5440)), where $d$ is the degeneracy of the input graph (which is even smaller than the treewidth).


---

### Answer by username_4 on 2015-10-25. Score: 1

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.396.4536) 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.


---

