Computer Science Colloquium
Testing for a Theta
Maria Chudnovsky
Columbia University
Friday, September 15, 2006, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 100121185
Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Hosts:
Michael Overtonoverton@cs.nyu.edu, (212) 9983121
Abstract
Recently a few new results appeared, providing polynomial time
algorithms for testing if a given graph contains certain induced subgraphs
(such as "pyramids", odd odd cycles and anticycles, and some others).
However, some seemingly similar problems (such as testing for the presence
of an induced cycle passing through two given vertices, or testing for
"prisms") are known to be NPcomplete. At the moment it is not clear what
causes this difference.
A "theta" is a graph consisting of three vertex disjoint induced paths
between two fixed vertices (the "ends"), such that there are no edges
between the interiors of different paths. In joint work with Paul Seymour
we were able to find a polynomial time algorithm to test if a graph
contains a theta. In fact, we prove a stronger result, that provides a
necessary and sufficient condition for a graph to contain a theta with a
given end. We prove that a graph G does not contain a theta with a given
end v, if and only if G has a certain structure; which can be tested for in
polynomial time.
Refreshments will be served
top  contact webmaster@cs.nyu.edu
