Fixed parameter tractability via Robertson-Seymour

Logic Seminar

Meeting Details

For more information about this meeting, contact Kristin Berrigan, Jan Reimann, Linda Westrick.

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

Date: 10/08/2019

Time: 2:30pm - 4:00pm