A glimpse on my PhD thesis

Prelegent(ci)

Marcin Pilipczuk

Afiliacja

Uniwersytet Warszawski

Termin

12 stycznia 2012 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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).

---