The standard parameterization of the Vertex Cover problem (Given an undirected graph G and k ∈ N as input, does G have a vertex cover of size at most k?) has the solution size k as the parameter. The following more challenging parameterization of Vertex Cover stems from the observation that the size MM of a maximum matching of G lower-bounds the size of any vertex cover of G: Does G have a vertex cover of size at most MM+k_μ? The parameter is the excess k_μ of the solution size over the lower bound MM. Razgon and O'Sullivan (ICALP 2008) showed that this above-guarantee parameterization of Vertex Cover is fixed parameter tractable and can be solved in time O~*(15~(kμ)), where the O~* notation hides polynomial factors. This was first improved to O~*(9~(kμ)) (Raman et al., ESA 2011), then to O~*(4~(kμ)) (Cygan et al., IPEC 2011, TOCT 2013), then to O~((2.618~(kμ)) (Narayanaswamy et al., STACS 2012) and finally to the current best bound O~*(2.3146~(kμ)) (Lokshtanov et al., TALG 2014). The last two bounds were in fact proven for a different parameter: namely, the excess kλ of the solution size over LP, the value of the linear programming relaxation of the standard LP formulation of Vertex Cover. Since LP ≥ MM for any graph, we have that k_λ ≤ k_μ for Yes instances. This is thus a stricter parameterization-the new parameter is, in general, smaller - and the running times carry over directly to the parameter k_μ. We investigate an even stricter parameterization of Vertex Cover, namely the excess k of the solution size over the quantity (2LP - MM). We ask: Given a graph G and k ∈ N as input, does G have a vertex cover of size at most (2LP - MM) + k? The parameter is k. It can be shown that (2LP - MM) is a lower bound on vertex cover size, and since LP ≥ MM we have that (2LP - MM) ≥ LP, and hence that k ≤ k_λ holds for Yes instances. Further, (k_λ - k) could be as large as (LP - MM) and - to the best of our knowledge - this difference cannot be expressed as a function of k_λ alone. These facts motivate and justify our choice of parameter: this is indeed a stricter parameterization whose tractability does not follow directly from known results. We show that Vertex Cover is fixed-parameter tractable for this stricter parameter k: We derive an algorithm which solves Vertex Cover in time O~*(3~k), thus pushing the envelope further on the parameterized tractability of Vertex Cover.
展开▼
