[Statseminars] Fwd: [Dmtcs] Maria Chudnovsky to speak on Monday 10/23 at 3:30

[Amy Mulholland]

>X-Original-To: dmtcs at cs.yale.edu
>Delivered-To: dmtcs at cs.yale.edu
>Date: Fri, 20 Oct 2006 13:00:19 -0400
>From: "Daniel A. Spielman" <spielman at cs.yale.edu>
>To: dmtcs <dmtcs at cs.yale.edu>, department-cs at cs.yale.edu
>User-Agent: Internet Messaging Program (IMP) H3 (4.0.5)
>X-Mailman-Approved-At: Fri, 20 Oct 2006 13:01:41 -0400
>Cc:
>Subject: [Dmtcs] Maria Chudnovsky to speak on Monday 10/23 at 3:30
>X-BeenThere: dmtcs at cs.yale.edu
>X-Mailman-Version: 2.1.5
>List-Id: Discrete Math and Theoretical Computer Science Seminar
>         <dmtcs.cs.yale.edu>
>List-Unsubscribe: <http://mailman.cs.yale.edu/mailman/listinfo/dmtcs>,
>         <mailto:dmtcs-request at cs.yale.edu?subject=unsubscribe>
>List-Archive: <http://mailman.cs.yale.edu/pipermail/dmtcs>
>List-Post: <mailto:dmtcs at cs.yale.edu>
>List-Help: <mailto:dmtcs-request at cs.yale.edu?subject=help>
>List-Subscribe: <http://mailman.cs.yale.edu/mailman/listinfo/dmtcs>,
>         <mailto:dmtcs-request at cs.yale.edu?subject=subscribe>
>Sender: dmtcs-bounces at cs.yale.edu
>X-YaleITSMailFilter: Version 1.2c (attachment(s) not renamed)
>X-Scanned-By: MIMEDefang 2.52 on 130.132.50.54
>
>
>Testing for a Theta
>Maria Chudnovsky
>Columbia University
>
>Monday, October 23rd at 3:30 in AKW 500
>
>ABSTRACT
>
>Recently, a few new results have 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 NP-complete. 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.
>
>             For more information, see 
> http://www.cs.yale.edu/homes/spielman/DMTCS/
>
>----------------------------------------------------------------
>This message was sent using IMP, the Internet Messaging Program.
>
>_______________________________________________
>Dmtcs mailing list
>Dmtcs at cs.yale.edu
>http://mailman.cs.yale.edu/mailman/listinfo/dmtcs