Marthe Bonamy

LIRMM

Graph pre-processing algorithms

Given a parameterized graph problem (vertex partition into k stable sets, or in a forest and at most k vertices, detection of a dominating set of size k, etc), we look into efficient (i.e. polynomial-time) algorithms to simplify an instance of that problem. "Simplify" may have different meanings depending on the desired result. Intuitively, if we try to k-color a graph G, and this graph G contains a vertex of degree at most k-1, we know this vertex will have no influence on the result and can thus be removed without any loss of information. After identifying other such simplification rules, we want to guarantee the efficiency of the corresponding pre-processing algorithm, at least on a subclass of graphs (for example planar graphs). Depending on the desired result, we can try to prove that the algorithm always outputs the empty graph, which ensures that the considered graph class always admit a solution (for example planar graphs for the problem of 4-coloring). We can more generally try to prove that the algorithm always outputs a graph of size bounded with a function of k, which ensures that for fixed k, we can decide in poly-time whether a solution exists, and exhibit one if any. This kind of result is interesting in particular for problems which are known to be NP-hard. Here we look into the Feedback Vertex Set problem (how many vertices do we have to remove from a graph to obtain a forest?) parameterized with the size of the solution (is removing k vertices enough?), in the setting of planar graphs. We present a linear-time pre-processing algorithm which outputs a planar graph on at most 13k vertices. This is a joint work with Lukasz Kowalik (University of Warsaw).