An Effective Upperbound on Treewidth Using Partial Fill-in of Separators
This work provides an incremental improvement in graph theory and algorithms, specifically for researchers and practitioners dealing with treewidth-based methods in areas like constraint satisfaction.
The paper tackles the problem of bounding treewidth in graphs by introducing a new method that partially fills in edges of a separator, rather than making it a full clique, resulting in a tighter upper bound. This approach is shown to be more effective for decomposing graphs and has applications in combinatorial algorithms and constraint satisfaction problems.
Partitioning a graph using graph separators, and particularly clique separators, are well-known techniques to decompose a graph into smaller units which can be treated independently. It was previously known that the treewidth was bounded above by the sum of the size of the separator plus the treewidth of disjoint components, and this was obtained by the heuristic of filling in all edges of the separator making it into a clique. In this paper, we present a new, tighter upper bound on the treewidth of a graph obtained by only partially filling in the edges of a separator. In particular, the method completes just those pairs of separator vertices that are adjacent to a common component, and indicates a more effective heuristic than filling in the entire separator. We discuss the relevance of this result for combinatorial algorithms and give an example of how the tighter bound can be exploited in the domain of constraint satisfaction problems.