Type = (l1,l2)
l1 = at least l1 incoming edges
l2 = at least l2 outgoing edges
for every node
Given two graphs CG and SG satisfying type (l1,l2),
find a graph TG satisfying:
Paths(TG) = Intersection(Expansion(Paths(SG)), Paths(CG))
You are paid 1/|TG| where |TG| is the number of edges of TG.
Type = pair of numbers
Raw materials: 2 graphs both satisfying the type.
Finished product: Traversal graph
Quality: 1/(number of edges)
What is the right price for a type?
What are the worst raw materials for a given type?