Hypertree and Connected Hypertree Decomposition


This page provides the tools and instances used in the experiments of the paper:

Sathiamoorthy Subbarayan and Henrik Reif Andersen,
Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs,
IJCAI 2007

Presentation Slides

 

Tools

The tools available below are Linux binaries.

CHTD
CHTD-NoIso
HTD
HTD-NoIso

Usage
A sample command line is: CHTD input.hg [timeLimit] [startWidth]
where, "input.hg" is the input hypergraph as specified in the 'hg' format below.
The optional "timeLimit" could be used to specify, of course, a time limit :-).
The optional "startWidth" is the width at which the tool starts the query sequence as specified in the paper.

Instances
The 12 instances used in the experiments are available in three formats:
HG : the hypergraph format used by our binaries above.
DBAI : the format used by HTDECOMP tool and the opt-k-decomp tools by Francesco Scarcello and Peter Harvey.
GRAPH : the format used by the QuickBB code by Vibhav Gogate.

Instance Sources
The five *.cp instances are configurations problems from CLib.
The five *.dag instances are from FaultTrees distributed by Antoine Rauzy.
The two *.smt instanes are from SMT (satisfiability modulo theory) problem hypergraphs given to me by Lucas Bordeaux.

The HG Format

The HG format is quite simple. The format is:

numVars numCons
s1 v11 v12 ... v1s1
s2 v21 v22 ... v2s2
s3 v31 v32 ... v3s3
.
.
.

where,
numVars: the number of variables
numCons: the number of constraints
si: size of the i'th hyperedge
vij: the j'th variable in the i'th hyperedge. Note, the variables are numbered starting from zero.
.

Related Online Links
Optkdecomp tool by Francesco Scarcello
Optkdecomp and Redkdecomp tools by Peter Harvey
HTDECOMP tool with several heuristics for hypertree decomposition
QuickBB tool, along with source code, by Vibhav Gogate for tree decomposition


For comments and suggestions please email me : sathi itu dk

Sathiamoorthy Subbarayan