```
```

## The Graph Realization problem:

Graph Realization is the problem of constructing a tree from a set of its edge-labeled paths. More formally, Given subsets P1,..Pn of {0,..,m-1}, find a tree T=(V,E) with E={0,..,m-1} such that every Pi is a path in T, or determine that no such tree exists.

Graph Realization was first defined by Tutte . Several polynomial algorithms for the problem were introduced in [1,3,4]. Graph Realization recently came back to awareness in computational molecular biology, in problems related to haplotype inference under the perfect phylogeny model .

GREAL is an implementation of the algorithm for Graph Realization of Gavril and Tamari . This algorithm runs in  O(nm2)time and  O(nm) space.

GREAL was written in C++. We supply here executables for Windows, Linux and SunOS. In addition to its standard interface, GREAL outputs the solution tree in a format that allows visualization using a graph drawing software .  See the Read Me file for details.

GREAL was written by Tamar Barzuza, under the supervision by Dr. Itsik Pe’er, Prof. Jacques Beckmann (Weizmann Institute) and Prof. Ron Shamir (Tel Aviv University).

The GREAL software is freely available for academic use. Interested users (academic and commercial) should contact Ron Shamir (rshamir AT tau dot ac dot il)

## An example:

For the ground set {0,1,2,3,4}and the subests P1={1,2,3,4},P2={0,2,3} and P3={0,1}, the graph realization is: Notice that we merge a path of dependent edges into one edge, such as 2 and 3 in this example. Edges are dependent if they always appear together in P1,..Pn.

Using the GREAL input and output formats (see  Read Me), the input  is the following hypergraph:

 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0

It indicates that E={0,..4} and that T must realize the paths {{1,2,3,4},{0,2,3},{0,1}}. This input is given in hypergraph.txt.

The output of GREAL is:
actual vertices:
0 = 0
1 = 1
2 = 2 3
3 = 4
realization:
 -1 1 -1 0 2 1 -1 -1 -1 -1 -1 -1 -1 -1 3 0 -1 -1 -1 -1 2 -1 3 -1 -1
The realization matrix is the adjacency matrix of T. It indicates that V={0,..4} and that E is constructed form edges (0,1),(2,4),(0,3),(0,4) with initial labeling of 1,3,0,2 respectively.
The actual vertices list indicates that this labeling of E should be changed such that 0 remains 0, 1 remains 1, 2 is replaced by 2,3; and 3 is replaced by 4. The tree drawn above is a result of running neato on this output of GREAL.

For more details see the Read Me file. For a more complex example of a hypergraph see hypergraph.txt.

## References:

  F. Gavril and R. Tamari (1983) An algorithm for constructing edge-trees from hypergraphs. Networks, 13:377-388
  W. T. Tutte (1958) A homotopy theorem for matroids I and II. Transactions of the American Mathematical Society, 18:144-174
  W. T. Tutte (1960) An algoritm for determining whether a given binary matroid is graphic. Proceedings of the American Mathematical Society, 11:905-917
  R. E. Bixby and D. K. Wagner (1988) An almost linear-time algorithm for graph realization. Mathematics of Operations Research, 13:99-123
  Gusfield D (2002) Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions. Proceedings of the Sixth Annual International Conference on Computational Biology (RECOMB '02), 166-175
  http://www.research.att.com/sw/tools/graphviz/