Vibhav Gogate



Vibhav Gogate and Rina Dechter, “A complete Anytime Algorithm for Treewidth,” In 20th Conference on Uncertainty in Artificial Intelligence (UAI), 2004. [ PDF ]

Software: Download the binaries


  • quickbb [option1] [option2] –cnffile CNFFILE

  • A description of the (input) CNF format is given here. Any graph can be written in this format. For example, a chain 1-2-3 can be specified as:

p cnf 3 2

1 2 0

2 3 0

The first line says that we are specifying the graph using 3 variables and 2 cliques (each edge is a clique. Trivially, you can specify a graph using its edges)

The second line describes the first clique between vertex 1 and 2. “0” is the delimiter which specifies end of line.

The third line describes the second clique between vertex 2 and vertex 3.

[option1] should be one of the following:

  1. --random-ordering: Branching performed in quickbb using random ordering

  2. --min-fill-ordering: Branching performed in quickbb using min-fill ordering

[option2] can be any of the following or combination thereof:

  1. --time [int]: Integer time-bound.

  2. --lb: Computes lb of the graph,

  3. --outfile [filename]: Store the output like treewidth, lb and the current best perfect elimination order (peo).

  4. --statfile [filename]: Program statistics. The statfile has the following format:

    1. row1:#vertices,

    2. row2: #edges

    3. row3: lb if --lb is used else 0,

    4. row4: an upper bound on the treewidth

    5. row5: Time elapsed,

    6. row6:Nodes Visited,

    7. row7:Nodes Pruned

    8. row8:1 if the treewidth given in row3 is exact and 0 if it is not.


  • /quickbb_64 –min-fill-ordering –lb –outfile myout –statfile mystat –cnffile ls8_normalized.cnf

This will run quickbb on the ls8_normalized.cnf instance. The ordering heuristic used is min-fill. The output will be stored in myout and the statistics will be stored in mystat