Seminário de Teoria da Computação Advances in Packing Directed Joins Aaron Williams -- University of Victoria-Canadá Segunda-feira, 25 de abril de 2005 ^^^^^^^^^^^^^^ <----- (Notem que é na próxima segunda) Sala 85 14:00hs Abstract: Edmonds and Giles conjectured that the maximum number of disjoint directed joins is equal to the smallest weight of a directed cut, in every weighted directed graph. The conjecture is true in several special cases, and is also true if the roles of directed joins and directed cuts are reversed, by the Lucchesi-Younger Theorem. Schrijver disproved the conjecture in general by providing the first counterexample. Twenty years later, Cornuéjols and Guenin discovered two more counterexamples by computer search. Despite its great potential significance, little progress has been made towards compiling a complete list of minimal counterexamples. One obstacle is the apparent complexity of the known counterexamples. In this paper, we offer a simple framework for understanding these counterexamples, and we use this framework to construct several new counterexamples. Then we prove that minimal counterexamples have a particular structure, and we use this structure to show that every "smallest" minimal counterexamples has now been found. In addition, we introduce an NP-completeness result for a more difficult problem. About Aaron Williams: - PhD candidate in Computer Science at University of Victoria (supervisor Wendy Myrvold and Frank Ruskey) - MMath in Combinatorics & Optimization at University of Waterloo (supervisor Bertrand Guenin) - Second trip to South America, but first time in Brazil!