Abstract
Let P be a fixed hereditary graph class. In the P-Completion problem, given a graph G and an integer k, we ask whether it is possible to add at most k edges to G to obtain a member of P. In the recent years completion problems received significant attention from the perspective of parameterized complexity, with the standard parameterization by k.
In our talk we first survey the history of the study of parameterized complexity of completion problems, including the breakthrough paper of Villanger, Heggernes, Paul, and Telle (SIAM J. Comp. 38(5):2007-2020, 2009) that settles fixed-parameter tractability of Interval Completion, as well as recent advancements on polynomial kernelization. Then, we move to the main topic, namely subexponential parameterized algorithms.
First fixed-parameter algorithms for completion problems focused mostly on the 'forbidden induced subgraphs' definition of the graph class P in question. In 2012 Fomin and Villanger (SIAM J. Comput. 42(6):2197-2216, 2013) came up with a novel idea to instead focus on some structural definition of the class P, trying to build the modified output graph by dynamic programming. Slightly simplifying, we may say that the main technical contribution of their work is a subexponential in k bound of reasonable 'partial chordal graphs' for an input instance (G,k) of Chordal Completion. Consequently, Chordal Completion can be solved in subexponential FPT time.
Following the approach of Fomin and Villanger, in the past three years subexponential parameterized algorithms were shown for the class of chain, split, threshold, trivially perfect, pseudosplit, and, most recently, proper interval and interval graphs. Moreover, a few lower bounds for related graph classes were found.
In the talk I will survey the above results, and sketch the main ideas behind them.