Working Seminar on Formal Models, Discrete Structures, and Algorithms

Fixed Parameter Extension Complexity

Hans Raj Tiwary (MFF UK)

When: Tuesday May 5, 10:00am

Where: room C417


An extension (extended formulation) of a polytope P is a polytope Q such that P is a projection of Q. Extension complexity of P measures the size of smallest Q such that Q is an extension of P. It has been shown recently that various problems associated with natural NP-hard combinatorial optimization problems, such as CUT, TSP, etc, have superpolynomial extension complexity. Some “easy” problems such as perfect matching also have been shown to have exponential extension complexity.

In this talk, I will give an introduction to extended formulations with a summary of known results. I will then discuss ways to apply this theory to the notion of FPT and W[n]-hardness and present some partial results.

A portion of the talk is based on joint work with Petr Kolman and Martin Koutecky.