| Next | 3.3- PhyloDAGs |
| Previous | 3.1- Hardness of approximation of phylograph |
| Up | 3- Phylographs and phyloDAGs |
There is a natural greedy algorithm for the Minimum Phylograph problem. In a phylograph, every character's induced subgraph consists of a single connected component, so the greedy algorithm ``grows'' a solution by iteratively adding an edge that maximally reduces the number of connected components.
The same notation needed to define the algorithm more precisely
can be used in the proof of its quality.
Given species
and characters
,
and a set of edges
define the ``cost'' of E to be
where
denotes the number of connected
components in the subgraph of
induced by the on-set of c.
Thus
, and
if E is a phylograph,
.
For any edge set E and any edge e,
let
be
the amount by which e decreases the cost f.
The greedy algorithm begins with each species an
isolated vertex, and iteratively adds the edge which maximally
decreases the cost, until the cost is 0.
In pseudocode:
¯¯¯Let i:=0 and
While
do
begin
Let i:= i+1
Let e be an edge maximizing
Let
end
Return the set
This complements the result of Theorem 17:
Minimum Phylograph is apparently hard to approximate to better than a factor
of
,
but easy to approximate to a factor
.
It would be of some interest to derive better bounds on
the constant c,
,
for which
-approximability is possible.
| Next | 3.3- PhyloDAGs |
| Previous | 3.1- Hardness of approximation of phylograph |
| Up | 3- Phylographs and phyloDAGs |
