Find Maximum Independent Set using Tree Decomposition of a Graph

[pps-19012]

Problem Description

Many problems that are NP-complete for arbitrary graphs can be solved efficiently (usually using dynamic programming) for graphs of bounded treewidth and its tree decomposition. The problem of finding the maximum independent set in a graph falls in this category.

Proposed Solution

Use dynamic programming approach for a graph with given tree decomposition to find maximum independent set.

This paper proposes a dynamic programming approach for finding MIS (and other interesting problems) for partial k-trees. The notion of partial k-tree in this paper is equivalent to a graph of treewidth at most k.

Alternatives Considered

The book Parametrized Algorithms introduces dynamic programming approach for weighted independent set using nice tree decompositions. Although, it is not directly useful, it can be used to formulate approach for our problem of finding MIS.

I couldn't find any solutions in Sagemath or elsewhere which finds MIS using tree decomposition.

Additional Information

I have already started implementing. The code can be found here; mis function takes graph and tree_decomposition as arguments and returns the maximum independent set and its cardinality.

Tree decomposition can be calculated using Sagemath's tree_decomposition module.

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

[pps-19012]

@mkoeppe Could you please help me identify in which module I should raise a PR for implementing this? The code is here. I have also tested it using a few families of graph.

[mkoeppe]

I'd like to defer to @dcoudert regarding this

[dcoudert]

I have some concern about your code.

1. it is not documented and so I don't understand the algorithm it implements
2. I have some doubt about the efficiency of the proposed method, in particular since it requires a tree-decomposition which is quite long to compute. Have you compared the running time of your algorithm, including the time to compute a tree-decomposition, with the running time of the methods we already have ?

[pps-19012]

@dcoudert Apologies for missing documentation.

1. I have updated my code here. I have explained how it uses DP to find MIS using tree decomposition. You can also refer to Page 5 of this for a better understanding.

2. The method which is already present in Sagemath computes maximal independent sets. To find maximum independent sets among these, we have to iterate through all the maximal independent sets. My algorithm directly returns the maximum independent set. For large graphs, computing maximal independent sets using Sage's algo itself is time consuming. Further iterating on that set to find maximum independent set will require even more time. Thus, we cannot make a direct comparison between the two implementations. I can make the comparison for the sake of it, but since we are not directly comparing, it might not be the best method. Please let me know what do you think of this.

Meanwhile, you can review this to see the efficiency of the proposed method. I have noted the running time for various graph sizes. These graphs belong to the family of graphs having pathwidth 2.

[dcoudert]

Check method independent_set https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.independent_set