Generating intervals

András Benczúr, Jörg Förster, Zoltán Király

Győri's theorem says that for a system of subintervals of a path the minimum size of a generating system (a set of intervals such that all given subinterval is the union of some of them) is equal to the maximum size of an independent subsystem (ie. subintervals I(1), I(2), ..., I(t) such that they cannot be generated by less then t generators, because for all 1<i<=t there is a point in I(i) such that not any of I(1), ..., I(i-1) contains that point).

Recently András Frank developed a new combinatorial algorithm for finding the minimum generator system and the maximum independent set even for intervals of a cycle. We implemented his algorithm.

For reading about the theoretical background, history and the implementation itself read the Thesis of Jörg (unzipped version) or our paper in progress (unzipped version).

There are three programs here, the first is for path, the second is for cycle and the third is for rectangles in a vertically convex region. All three was written by Jörg Förster.

The program Gyori in directory Path (the compiled code is for Solaris 2.5.1) computes a minimum generating system and a maximum independent subsystem of a family of a mainpath's subpaths (or analogously for a system of a maininterval`s subintervals). We consider the mainpath and all the subpaths drawn horizontally and having integer endpoints. A makefile is included, however, the paths for the libraries (especially for xlib) and include files may have to be reset to work on your system.

You can either copy the program and/or sourcecode to your directory. When you execute the file 'Gyori' you are prompted for an input file.

As an input the program needs a file in the following format:

X Y     -- The 1st line:        the left and right coordinates of the mainpath.
size    -- The 2nd line:        where size is the no. of subpaths.
x y     -- All following lines: left and right coord. of the subpaths.
x y
x y
.
.
.

Such an input can also be generated with the program 'testgen' where you are prompted for some parameters of the mainpath and subfamily and a seed for generating an arbitrary system. The program 'testgen' writes the input in the file 'test.in'.

The next input you are prompted for by 'Gyori' is if you want to enter a freebie generator (Type 'n' if you don't know what to do!) If you chose yes, you are asked to type in the name of the file containing the freebie generator.

This file has to have the following format:

size    -- The 1st line:        where size is the no. of freebie generator.
x y     -- All following lines: left and right coord. of the freebie generator.
x y
x y
.
.
.

The last question you are asked is if the interval system should be showed graphically in a separate window. Answer yes ONLY IF you have an xlib connection to the server the program is running on. In this window you can obtain online help by pushing the 'H'-key of the keyboard. By clicking on any orange 'edge' the directly following members of the poset are being highlighted.

The Output of the program is written to the files Generator and Independent.

In directory Circ the "almost-finished" program Gyori (the compiled code is for Solaris 2.5.1) does the same thing but for intervals of a cycle.

See also the graphical program in the directory Rectangle, which demonstrates Győri`s theorem for a rectangle cover of a vertically convex polygon.

Good luck!