# 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