Fixed parameter tractability via Robertson-Seymour
Speaker: Caitlin Lienkaemper, Penn State University
Abstract: Many NP complete problems are nonetheless practically solvable for many natural families of input. This often results from “fixed parameter tractability”—a problem is said to be fixed parameter tractable with parameter k if it is solvable in running time bounded by some function f(k)•p(n), where n is the size of the input, p is a fixed polynomial, and f is any computable function. For instance, the problem of determining whether a graph has a vertex cover of size k is NP-complete, but can be solved in O(nk+1.274^k) time. In this talk, we discuss how the Robertson-Seymour graph minor theorem gives (non-constructive) proofs that many graph properties are fixed parameter tractable.
Room Reservation Information
Room Number: 315 McAllister
Time: 2:30pm - 4:00pm