What is Separator concept in Tree Decomposition?

Question

I am trying to understand the Maximum Independent Set problem in Tree Decomposition using dynamic programming. However I am not being able to get the notion of "separator" in the proposed algorithms. Can someone make me clear on this. Thanks in advance.

Answer 1

A separator is a subset of vertices whose removal leaves a graph with several connected components. A separator is balanced if every connected component has less than half the number of vertices compared to the original graph.

A graph with low treewidth has a small balanced separator. More precisely, a graph of treewidth k has a balanced separator with at most k+1 vertices.

Algorithms exploit this as follows:

• remove a small balanced separator from the graph

• recursively find an optimum solution for the connected components

• add the separator again (possibly vertex by vertex), and use the solutions for the connected components to find an optimum solution for the whole graph.

To make the above scheme efficient, a few requirements need to be met:

• the separator in the first step is small (that is, of constant size)

• the connected components in the second step are substantially smaller number of vertices than the original graph (that is, a constant fraction, e.g. 1/2).

• the above properties are inherited to induced subgraphs (otherwise you cannot recurse efficiently)

• the partial optimum solutions for the connected components can be efficiently combined to an optimum solution for the whole graph

These requirements are met by graphs of low treewidth - except the last one: this one is specific for each optimization problem, and this is what algorithm designers wrote research papers about.

(Image taken from the wikipedia article on vertex separator.)