Aniket Mane

Maximum weight connected subgraph of a graph with bounded tree-width

jeudi 21 mai 2015, 13h30 - 14h30

Salle de réunion, espace Turing

We consider a graph


with weights assigned to its nodes. The aim is to find the maximum weighted connected subgraph of the graph


. This problem has been found to be NP-hard on general graphs. Hence, it is necessary to restrict it to certain classes of graphs. The problem has already been solved on sequences by Ruzzo and Tompa. We reinterprete the solution given by them on sequences and extend a similar idea to trees.
It has been found that some problems can be solved with better complexity on graphs with bounded treewidth. Hence, we choose to tackle this problem on graphs of bounded treewidth. The process involves computing a tree decomposition of the given graph. The width of this decomposition is bounded by a pre-specified number


. Once, we have the tree decomposition, we apply dynamic programming to the problem and try to define the rules for the same. The final step consists of properly defining the constraints under
which a subtree from the given tree decomposition is chosen.