Haven (graph theory)

In graph theory, a haven is a concept used to define the treewidth of a graph. It provides an alternative, arguably more intuitive, characterization of treewidth compared to the formal definition involving tree decompositions. Specifically, a haven of order k in a graph G is a set of connected subgraphs of G such that:

1. No two subgraphs in the haven are adjacent.

2. For any set of fewer than k vertices in G, at least one subgraph in the haven remains connected after those vertices are removed from the graph.

More formally, a haven of order k is a function β that maps each set S of fewer than k vertices of G to a connected component β(S) of G - S (the graph obtained by removing the vertices in S from G) such that:

If S ⊆ T where S and T are sets of vertices in G with |S| < k and |T| < k, then β(T) ⊆ β(S).

The treewidth of a graph G is the maximum order k of a haven in G, minus one. In other words, treewidth(G) = max {k | there exists a haven of order k+1 in G} - 1.

The haven characterization highlights the idea that high treewidth implies the existence of a "hiding strategy" that can avoid a small number of removed vertices. Think of the haven as a collection of "safe" locations. No matter where you remove a small number of nodes, there's always at least one safe connected region remaining. The larger the size of this "small number," the higher the treewidth.