PACE 2019 (Track Hypertree Width/Exact)

Exact 2a. Hypertree Width/Exact


The hypertree decomposition has to be optimal, i.e., of hypertree width.


We anticipate submissions to be based on a provably optimal algorithm, although we do not make this a formal requirement. Instead, if your submission halts on some instance within the allotted time and produces a solution that is known to be non-optimal, the submission will be disqualified. We also do not prescribe the algorithmic paradigm that is to be used; if a SAT or SMT-solver based submission consistently outperforms more direct approaches, this will be valuable information.



There are 100 public benchmark instances, labeled htd-exact_001.hgr, htd-exact_003.hgr, … to htd-exact_199.hgr.

Larger numbers in the filename should (as a rule of thumb) correspond to harder instances. The odd instances are public and the even instances will be provided later (secret).

For verification purposes, we also publish the sha1sum of the public archive:

SHA1 sum filename
478afc600c11f98b20c969ecd5ff4a1badbabebc pace2019-htd-exact-public.tar.bz2

For individual files we refer to Download SHA1 sums