Dualization code

Dualization in Integer Boxes

The input to the dualization code is a set of vectors A in an integral box C. The ouptut is a set of vectors in the same box, that represent the complements of the maximal independent elements of the monotone system defined by A.

Below is a detailed description of the parameters, input and output files, together with some examples and downloadable executables.

Calling the program

"dual InputFileName OutputFileName"

InputFileName: the name of the file containing the input hypergragh (or vector family).
OutputFileName: the name of the file containing the output dual hypergragh (or vector family).
The format of both input and output files is the following:
The first line contains n and c, where
- n is the dimension (the number of variables), and
- c is the maximum size of the box (c=1 in case of hypergraphs).
The rest of the lines in these files contain the hyperedges (or vectors) of the hypergraph, one per line, separated by spaces (see examples below).

Important remarks

All files must be in the same directory where the program is to be run.
If the code finds the file OutputFileName in the same dierctory containing a partial (possibly empty) list of maximal independent elements, then it will proceed to complete this partial list, and generates the rest.
These codes are provided as "research ware", and in particular, the usually tedious and oracle dependent data consistency checks are not included. Please make sure that the input files adhere to the syntax we describe below (and if you provide a partial list also as input, that must indeed include minimal/maximal elements for the specified monotone property).

Integer points in [0,5]²: "C:\> dual a1.p a1.d "

If the file a1.p contains:
2 5
1 4
3 3
4 0

then the output file a1.d contains:
2 5
5 0
3 2
2 3
Note that these vectors are the complements of maximal independent elements shown in the figure to the left, i.e. a1.d contains (5,5)-(0,5),(5,5)-(2,3), and (5,5)-(3,2))

Hypergraph on 8 vertices (integer points in [0,1]⁸): "C:\> dual a2.p a2.d"

If the file a2.p represents the hypergraph H={{1,2},{3,4},{5,6},{7,8}}:
8 1
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1

then the output file a2.d represents the dual hypergraph

H^d={{1,3,5,7},{1,3,5,8},{1,3,6,7},{1,3,,6,8},...,{2,4,6,8}}

containing all minimal transversals of H:

8 1
0 1 0 1 0 1 0 1
0 1 0 1 1 0 0 1
0 1 1 0 0 1 0 1
0 1 1 0 1 0 0 1
0 1 1 0 1 0 1 0
0 1 0 1 0 1 1 0
0 1 1 0 0 1 1 0
0 1 0 1 1 0 1 0
1 0 1 0 0 1 1 0
1 0 1 0 0 1 0 1
1 0 1 0 1 0 0 1
1 0 1 0 1 0 1 0
1 0 0 1 1 0 0 1
1 0 0 1 1 0 1 0
1 0 0 1 0 1 0 1
1 0 0 1 0 1 1 0

Download the program