Format - Hypertree decomposition (Draft Updated 2018-12-02)

Checker

See: htd_validate

Input Format

Hypergraph (.hgr)

The hypergraph format extends the PACE2016 and PACE2017 graph format.

Example:

c This file describes a hypergraph in htd PACE2019 format
c with 6 vertices and 4 hyperedges
p htd 6 4
1 1 2 3
2 2 3 4
c this is a comment and will be ignored
3 3 4 5
4 4 5 6

Description

Hypertree Decomposition Format (.htd)

See: https://arxiv.org/abs/1611.01090 for a compact definition of various hypertree decompositions.

c This file describes a hypertree decomposition
c with 5 bags, width 2 
c for a hypergraph with 5 vertices and 5 hyperedges
s htd 5 2 5 5
b 1 1 2 3
b 2 2 3 4 1
b 3 3 4 5 1 2
b 4 4 5 1 2 3
b 5 5 1 2
2 1
3 2
4 3
5 4
w 1 1 0
w 1 2 0
w 1 3 1
w 1 4 0
w 1 5 1
c
w 2 1 0
w 2 2 0
w 2 3 1
w 2 4 0
w 2 5 1
c
w 3 1 0
w 3 2 0
w 3 3 1
w 3 4 0
w 3 5 1
c
w 4 1 1
w 4 2 0
w 4 3 1
w 4 4 0
w 4 5 0
c
w 5 1 0
w 5 2 0
w 5 3 0
w 5 4 0
w 5 5 1

Description