Fully polynomial parameterized algorithms

PhD Qualifying Examination


Title: "Fully polynomial parameterized algorithms"

by

Mr. Pavel HUDEC


Abstract:

Numerous graph problems with extensive real-world applications have been proven 
to be NP-hard, making it unlikely we will ever find an efficient algorithm for 
them. Luckily, we are often only interested in specific instances which can be 
described by a value of some graph parameter being bounded. This motivates the 
study of parameterized algorithms whose complexity also depends on the value of 
the parameter.

Our survey introduces modern structural graph parameters, relates them with 
each other, and shows some general and specific ways to design parameterized 
algorithms for them. We focus on the interplay of parameterization with other 
algorithmic techniques used in handling hard problems -- namely randomization 
and approximation. Recently, there has been an explosion of interest in 
establishing relative hardness of problems in P. We focus on whether there 
exist fully polynomial parameterized algorithms breaking the general complexity 
bounds when the respective parameter is bounded.


Date:                   Thursday, 5 September 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Dr. Dimitris Papadopoulos (Chairperson)
                        Dr. Sunil Arya
                        Prof. Siu-Wing Cheng