Algorithms and Data
Spring 2010

Due date: February 3, 2010
At beginning of lecture

Polynomial Time Algorithms with High Exponent

Problem 3.1:

Solve problem 4.30 (Steiner tree problem) given in the text book.

Problem 3.2:

Design a polynomial-time algorithm for the restricted LeafCovering problem
described below.
What this demonstrates: When a big structure is implicitly 
represented succinctly we may be able to 
work with the succinct representation to invent a polynomial-time algorithm.


Terminology:
Ti=(Vi,Ei) is a tree with nodes Vi and edges Ei.
(view the i as subscripts)
DAG = directed acyclic graph

Definition: Graph Cartesian product 
  Given n directed trees T1, ..., Tn,  
  where Ti=(Vi,Ei), the graph Cartesian product
  is a DAG
  TT(T1, ..., Tn) that has as nodes the tuples (v1, ... ,vn) where vi in Vi and
  the following edges:
     Node (v1, ..., vi, ..., vn) has as children all nodes
     (v1, ..., vi', ..., vn), where vi' is a child of vi in Ti, and all
     other components are the same.


The LeafCovering Problem
-------------------------

  INSTANCE:
  Given n directed trees T1, ..., Tn defining the 
  graph Cartesian product TT(T1, ... .Tn),
  and a set of nodes, M, in TT(T1, ... .Tn).
  We assume that M only contains 2 elements.

  QUESTION:
  Does each leaf in TT(T1, ..., Tn) have some ancestor in M?
  The answer is either "yes" or "no". 

As a connection to your Theory of Computation course:
LeafCovering is co-NP hard(when M may be arbitrary, not of size 2).

Example of graph Cartesian product:

Tree T1
Baum : Node | Leaf.

Tree T2:
Exp : Lit | Bin.
Bin : Add | Sub.

TT(T1,T2):
/home/lieber/.www/courses/algorithms/cs4800/sp10/homeworks/hw3/graphCartesianproduct1.png

This looks like a rather abstract problem but it 
has a very useful application:
It is a type checking problem that multiple dispatch
programming systems must answer. 

Can you avoid an explicit representation
of the graph Cartesian product which would clearly lead to an
exponential algorithm?

How would you solve the problem if |M|=3?