I'm trying to implement or find an algorithm that can find a minimal tree decomposition of a small graph; if need be by exhaustive search. I'm sure there is something better than generating all possible subsets and testing them, but I can't figure one out.

I already know that the treewidth of my graph (the 3-dimensional cube) is 3 or 4. I have a decomposition with k=4, and it contains the 4-clique as a minor so it has treewidth >=3. Now according to Bodlaender and Thilikos, "a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor", which appears to imply that the cube graph itself has treewidth at most three (otherwise "treewidth at most three" would already exclude the cube as a minor). I've also written (extremely inefficient) minor-generators and isomorphism testers, which failed to find one of the forbidden minors for partial 3-trees in it.

(And yes, this is homework, so I need just a pointer, no solution.)

## Tree decomposition of a small graph

**Moderators:** phlip, Moderators General, Prelates

- Arancaytar
**Posts:**1642**Joined:**Thu Mar 15, 2007 12:54 am UTC**Location:**52.44°N, 13.55°E-
**Contact:**

### Tree decomposition of a small graph

"You cannot dual-wield the sharks. One is enough." -Our DM.

- Arancaytar
**Posts:**1642**Joined:**Thu Mar 15, 2007 12:54 am UTC**Location:**52.44°N, 13.55°E-
**Contact:**

### Re: Tree decomposition of a small graph

Never mind, got it in k=3.

Edit: Mh; the total problem has this as a subgraph, and the whole thing might be treewidth >= 4. Unfortunately, I haven't cracked that one yet.

An interesting approach for an exhaustive search would be to deconstruct it as a partial k-tree in reverse: Pick any node with degree <= k, select (or build) a k-clique that contains all nodes it is connected to, and remove it as an apex. Repeat until <= k nodes are left or all nodes have degree >k. The chain of removed nodes and cliques, in reverse, can be used to generate the node->parent list of a tree decomposition.

The "select or build a clique" is obviously very expensive if the degree is <k, since we have to try many possible cliques rather than building one from the adjacent nodes.

Edit: Mh; the total problem has this as a subgraph, and the whole thing might be treewidth >= 4. Unfortunately, I haven't cracked that one yet.

An interesting approach for an exhaustive search would be to deconstruct it as a partial k-tree in reverse: Pick any node with degree <= k, select (or build) a k-clique that contains all nodes it is connected to, and remove it as an apex. Repeat until <= k nodes are left or all nodes have degree >k. The chain of removed nodes and cliques, in reverse, can be used to generate the node->parent list of a tree decomposition.

The "select or build a clique" is obviously very expensive if the degree is <k, since we have to try many possible cliques rather than building one from the adjacent nodes.

"You cannot dual-wield the sharks. One is enough." -Our DM.

### Who is online

Users browsing this forum: No registered users and 6 guests