3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Independent set problem is P in graphs of bounded clique width but not every dense graph is bounded clique width. $\endgroup$ – Saeed Aug 27 '15 at 20:44
  • $\begingroup$ 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? $\endgroup$ – daniello Sep 2 '15 at 8:04
  • $\begingroup$ @daniello, I'm mainly interested in solving these problem efficiently. $\endgroup$ – user35296 Sep 10 '15 at 19:21
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.