Green's Theorem and Isolation in Planar Graphs

Meeting Time: Apr. 37, 2009, 2:00-2:50pm

Abstract: We consider the following computational tasks.

(1) Given a directed graph G. Design a weight function for the edges so that between every pair of vertices u and v, among all u-to-v hs in G, the minimum weight u-to-v path is unique.
(2) Given an undirected bipartite graph G. Design a weight function the edges so that among all the perfect matchings of G, the mimum weight perfect matching is unique.

Designing such "isolating" weight functions that are space-efficiently computable and polynomially bounded will imply major results in complexity theory and is an outstanding open problem. In this talk we show a simple application of a theorem due to 19th century British mathematician and physicist George Green to the above-mentioned isolation problems for the special case of planar graphs. This is a joint work with Raghunath Tewari.