Computing optimal discrete Morse functionsAlgebra & Discrete Mathematics
|Michael Joswig, TU Darmstadt and MSRI
|Fri, Sep 29 2006, 12:10PM
Morse matchings capture the essential structural information of discrete Morse functions, as introduced by Forman. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results. For the purpose of understanding the talk no knowledge in either classical or discrete Morse theory is assumed. (Joint work with Marc E. Pfetsch (ZIB Berlin)).