You are not logged in |
A glimpse on my PhD thesis
- Speaker(s)
- Marcin Pilipczuk
- Affiliation
- Uniwersytet Warszawski
- Date
- Jan. 12, 2012, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
In my talk I will present the main results of my PhD thesis. I plan to focus mostly on the background of my research, motivation, and present a very general overview of the techniques - without any technical details.
The talk will be divided into two parts. The first part, titled `Beyond 2^n', is devoted to the main line of research in moderately-exponential algorithms: can NP-hard problems be solved faster than the naive brute-force search (or straightforward dynamic programming)? In many cases, the brute-force solution or the DP one runs in 2^n time, where n is the number of vertices, variables or other entities in the considered problem. I will briefly summarize known approaches how to `break the 2^n barrier', and talk about the results of the thesis: algorithms for Capacitated Dominating Set (SWAT'10), Minimum Maximal Irredundant Set (CIAC'10), and, finally, a scheduling problem denoted 1|prec|sum C_i (ESA'11).
In the second part I will move to the area of fixed-parameter tractability. The main topic of this part will be the parameterized complexity of graph separation problems. I will present the background and the current state of this area and give a glimpse of the techniques used in the main contribution of the thesis: a fixed-parameter algorithm for the Subset Feedback Vertex Set problem (ICALP'11). I will conclude with a very short note on the last result of the dissertation: kernelization hardness of connectivity problems in graphs of bounded degeneracy (WG'10).
The talk will be divided into two parts. The first part, titled `Beyond 2^n', is devoted to the main line of research in moderately-exponential algorithms: can NP-hard problems be solved faster than the naive brute-force search (or straightforward dynamic programming)? In many cases, the brute-force solution or the DP one runs in 2^n time, where n is the number of vertices, variables or other entities in the considered problem. I will briefly summarize known approaches how to `break the 2^n barrier', and talk about the results of the thesis: algorithms for Capacitated Dominating Set (SWAT'10), Minimum Maximal Irredundant Set (CIAC'10), and, finally, a scheduling problem denoted 1|prec|sum C_i (ESA'11).
In the second part I will move to the area of fixed-parameter tractability. The main topic of this part will be the parameterized complexity of graph separation problems. I will present the background and the current state of this area and give a glimpse of the techniques used in the main contribution of the thesis: a fixed-parameter algorithm for the Subset Feedback Vertex Set problem (ICALP'11). I will conclude with a very short note on the last result of the dissertation: kernelization hardness of connectivity problems in graphs of bounded degeneracy (WG'10).
