## 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

- Line separator ‘\n’
- Lines starting with character c are interpreted as comments
- Vertices are consecutively numbered from 1 to n
- Problem description
- Form “p htd NumVertices NumHyperedges”
- Line starting with character p
- followed by the problem descriptor htd
- followed by number of vertices n
- followed by number of hyperedges m
- each separated by space each time

- Unique (No other line may start with p)
- Has to be the first line (except comments)

- Form “p htd NumVertices NumHyperedges”
- Remaining lines indicate a hyperedge
- consisting of decimal integers separated by space
- Starting with an integer that identifies the number of the hyperedge
- followed by the hyperedge
*Line: “1 1 2 3\n” indicates a hyperedge No 1 on vertices 1, 2, and 3*

- Empty lines or lines consisting of spaces may occur and only will be ignored
- Hypergraphs may contain isolated vertices, multiple hyperedges, and loops

### 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

- Line separator ‘\n’
- Lines starting with character c are interpreted as comments
- Vertices are consecutively numbered from 1 to n
- Solution description
- Form “s htd NumBags Width NumVertices NumHyperedges”
- Line starting with character s
- followed by the problem descriptor htd
- followed by number l of bags
- followed by the computed width
- followed by number n of vertices
- followed by number m of hyperedges
- each separated by space each time

- Unique (No other line may start with s)
- Has to be the first line (except comments)

- Form “s htd NumBags Width NumVertices NumHyperedges”
- Bag description
- BagIDs run consecutively from 1 to l
- Form “b BagID Vertex1 Vertex2 Vertex3 …”
- Lines starting with character b
- followed by an identifier of the bag
- followed by the contents of the bag
- each separated by space each time

- Example: “b 4 3 4 6 7”
- specifies that bag number 4
- contains the vertices 3, 4, 6, and 7 of the original hypergraph

- Bags may be empty
- Bags can contain at most z many vertices
- For every bag i, there must be exactly one line starting with b i.

- Width description
- Describe the width function mapping for the bags
- Value is in {0,1}
- Form “w BagID Hyperedge Value”
- Lines starting with character w
- followed by an identifier for the bag
- followed by the hyperedge
- followed by the value in {0,1} the function maps to
- each separated by space each time

- In order to save space we allow to skip width descriptions for (bag,hyperedge) -> 0 (i.e., if the function is not specified for a (bag,hyperedge), we implicitly assume value 0.)

- Tree description
- NodeIDs run consecutively from 1 to l
- Lines not starting with a character in {c,s,b,w} indicate an edge in the tree decomposition
- Form: “Node1 Node2”
- Lines starting with an identifier Node1 of the parent node
- followed by an identifier Node2 of the child node
- each separated by space each time

- The graph described in this way must be a tree, i.e., root nodes do not have a preceding node

- Empty lines or lines consisting of spaces may occur and only will be ignored