Tree decomposition of a small graph

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
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

Postby Arancaytar » Sun Nov 06, 2011 9:57 pm UTC

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.)
"You cannot dual-wield the sharks. One is enough." -Our DM.
Image

User avatar
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

Postby Arancaytar » Sun Nov 06, 2011 11:01 pm UTC

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.
"You cannot dual-wield the sharks. One is enough." -Our DM.
Image


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests