Chaire Aisenstadt 2006-2007 Aisenstadt Chair
Professor Paul Seymour
"Induced subgraph testing"
How hard is it to test whether an input graph has an induced subgraph in some fixed family of graphs? This depends on the family, but there are very few nontrivial families for which a polynomial-time algorithm is known. We survey some of these.
In particular, what about testing whether the input graph contains a "theta" (an induced subgraph consisting of two nonadjacent vertices joined by three vertex-disjoint paths). For instance, line graphs do not contain thetas, so the question is not trivial. Indeed, this has been an open question of some interest since a number of very similar questions are known to be NP-complete. We now have a polynomial-time algorithm.
The algorithm consists of a number of applications of a subroutine to test whether three given vertices are in an induced tree. So when are three given vertices in such a tree? This question in turn has a surprisingly neat answer; there is a structural characterization of the graphs in which no such tree exists (the graph has to admit a sort of generalized line graph structure), and we can test for this structure.
Joint work with Maria Chudnovsky (Columbia University).
Le mercredi 13 décembre 2006 / Wednesday, December 13, 2006
16 h / 4:00 pm
Université de Montréal, Pavillon André-Aisenstadt
2920, ch. de la Tour
Salle / Room 6214
"The Caccetta-Häggkvist conjecture"
This conjecture is a well-known open problem dating from 1978. In its simplest form, it asserts that for any integer k > 0, if G is a directed graph without parallel edges, and every vertex has outdegree at least |V(G)|/k, then there is a directed cycle of length at most k. This is easy for k = 1,2, but for k = 3 is still open.
This talk will be a survey of the problem and of our recent work on it: related conjectures, partial results, approaches and counterexamples.
Joint work with Maria Chudnovsky and Blair Sullivan.
Le vendredi 15 décembre 2006 / Friday, December 15, 2006
14 h / 2:00 pm
Université de Montréal
Pavillon André-Aisenstadt, 2920, ch. de la Tour
Salle / Room 6214