Calculate Treewidth

Question

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))

---

Examples:

[(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.

Answer 1

Octave, 195 bytes

function x=F(a)r=rows(a);P=perms(s=1:r);x=r;for m=s;b=a;n=0;for z=P(m,:);(T=sum(b)(z))&&{b|=(k=accumarray(nchoosek(find(b(z,:)),2),1,[r r]))|k';n=max(T,n);b(z,:)=0;b(:,z)=0}{4};end;x=min(x,n);end

A function that takes as input an adjacency matrix. It consumes large amount of memory so it is useless if number of vertices is more than 10-12.

• there is no need to endfunction however it should be added to tio.

Try it online!

Ungolfed:

function min_width = treewidth(graph_adj)
    Nvertices = rows(graph_adj)
    Permutations = perms(1:Nvertices);                                                            % do not try it for large number of vertices
    min_width = Nvertices;
    for v = 1:Nvertices;
        new_graph=graph_adj;
        max_neighbors=0;
        for p = Permutations(v,:)
            Nneighbors=sum(new_graph)(p);
            if(Nneighbors)>0
                connection=accumarray(nchoosek(find(new_graph(p,:)),2),1,[Nvertices Nvertices]);  % connect all neighbors
                new_graph|=connection|connection';                                                % make the adjacency matrix symmetric
                new_graph(p,:)=0;new_graph(:,p)=0;                                                % eliminate the vertex
                max_neighbors=max(Nneighbors,max_neighbors);
            end
        end
        min_width=min(min_width,max_neighbors);
    end
end

Answer 2

SageMath , 29 bytes noncompeting*

lambda L:Graph(L).treewidth()

*This answer posted before OP's change of the question that "Builtins are banned", so I maked it noncompeting .

Online Demo!

Answer 3

Haskell (Lambdabot), 329 321 245 bytes

Here's my solution, thanks to the flexibility of the input it works on graphs with graphs containing any type that is an instance of Eq.

(&)=elem
l=length
t n g s=last$minimum[max(t n g b)$t(n++b)g$s\\b|b<-filterM(\_->[0>1,1>0])s,l b==div(l s)2]:[l[d|d<-fst g,not$d&n,d/=s!!0,(d&)$foldr(\x y->last$y:[x++y|any(&y)x])[s!!0]$join(>>)[e|e<-snd g,all(&(s!!0:d:n))e]]|1==l s]
w=t[]<*>fst

Try it online!

Ungolfed version:

type Vertex a = a
type Edge a   = [Vertex a]
type Graph a  = ([Vertex a],[Edge a])

vertices = fst
edges = snd

-- This corresponds to the function w
treeWidth :: (Eq a) => Graph a -> Int
treeWidth g = recTreeWidth g [] (vertices g)

-- This is the base case (length s == 1) of t
recTreeWidth graph left [v] =
    length [ w | w <- vertices graph
               , w `notElem` left
               , w /= v
               , w `elem` reachable (subGraph w)
           ]

  where subGraph w = [ e | e <- edges graph, all (`elem` v:w:left) e ]

        reachable g = foldr accumulateReachable [v] (g>>g)
        accumulateReachable x y = if any (`elem` y) x
                                  then x++y
                                  else y

-- This is the other case of t
recTreeWidth graph left sub =
  minimum [ comp sub' | sub' <- filterM (const [False,True]) sub
                      , length sub' == div (length sub) 2
          ]

  where comp b = max (recTreeWidth graph left b)
                     (recTreeWidth graph (left++b) (sub\\b))