Searching for better fill-in

• The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.
• The k  -Vertex Eulerian Subgraph problem is W[1]W[1]-hard when parameterized by k.
• The treewidth of minimal connected odd graphs with minimal number of edges is at most three.

Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H  ? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time f(k)|G|O(1)f(k)|G|O(1) decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT.