The treewidth of an undirected graph is a very important concept in Graph Theory. Tons of graph algorithms have been invented which run fast if you have a decomposition of the graph with small treewidth.
The treewidth is often defined in terms of tree decompositions. Here's a graph and a tree decomposition of that graph, courtesy of Wikipedia:
A tree decomposition is a tree where each vertex is associated with a subset of the vertices of the original graph, with the following properties:
- Every vertex in the original graph is in at least one of the subsets.
- Every edge in the original graph has both of its vertices in at least one of the subsets.
- All of the vertices in the decomposition whose subsets contain a given original vertex are connected.
You can check that the above decomposition follows these rules. The width of a tree decomposition is the size of its largest subset, minus one. Therefore, it is two for the above decomposition. The treewidth of a graph is the smallest width of any tree decomposition of that graph.
In this challenge, you will be given a connected, undirected graph, and you must find its treewidth.
While finding tree decompositions is hard, there are other ways to calculate the treewidth. The Wikipedia page has more info, but one method of calculating treewidth not mentioned there which is often used in algorithms to calculate the treewidth is the minimum elimination ordering width. See here for a paper using this fact.
In an elimination ordering, one eliminates all of the vertices of a graph one at a time. When each vertex is eliminated, edges are added connecting all of that vertex's neighbors to each other. This is repeated until all of the vertices are gone. The elimination ordering width is the largest number of neighbors that any vertex which is being eliminated has during this process. The treewidth is equal to the minimum over all orderings of the elimination ordering width. Here is an example program using this fact to calculate the treewidth:
import itertools def elimination_width(graph): max_neighbors = 0 for i in sorted(set(itertools.chain.from_iterable(graph))): neighbors = set([a for (a, b) in graph if b == i] + [b for (a, b) in graph if a == i]) max_neighbors = max(len(neighbors), max_neighbors) graph = [edge for edge in graph if i not in edge] + [(a, b) for a in neighbors for b in neighbors if a < b] return max_neighbors def treewidth(graph): vertices = list(set(itertools.chain.from_iterable(graph))) min_width = len(vertices) for permutation in itertools.permutations(vertices): new_graph = [(permutation[vertices.index(a)], permutation[vertices.index(b)]) for (a, b) in graph] min_width = min(elimination_width(new_graph), min_width) return min_width if __name__ == '__main__': graph = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('b', 'g'), ('c', 'd'), ('c', 'e'), ('d', 'e'), ('e', 'g'), ('e', 'h'), ('f', 'g'), ('g', 'h')] print(treewidth(graph))
[(0, 1), (0, 2), (0, 3), (2, 4), (3, 5)] 1 [(0, 1), (0, 2), (1, 2), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (4, 6), (4, 7), (5, 6), (6, 7)] 2 [(0, 1), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 7), (5, 8), (6, 7), (7, 8)] 3 [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 4
You will receive the graph as input, and you must return the treewidth as output. The input format is flexible. You may take a list of edges, an adjacency map, or an adjacency matrix as input. If you'd like to use another input format, ask in the comments. You may assume the input is connected, and you may build that assumption into your input format, e.g. by using a list of edges.
EDIT: Built-in operations which calculate treewidth are not allowed. I apologize for not specifying this up front.
Shortest code wins.