Parameterized algorithms for minimum sum vertex cover

A minimum sum vertex cover of an n-vertex graph G is a bijection ϕ: V ( G ) → [ n ] that minimizes the cost ∑ { u, v } ∈ E ( G ) min ⁡ { ϕ ( u ), ϕ ( v ) }. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is 16/9 [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than 1. 014 for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. – MSVC can be solved in 2 2 O ( k ) n O ( 1 ) time, where k is the size of a minimum vertex cover. – MSVC can be solved in f ( k ) ⋅ n O ( 1 ) time for some computable function f, where k is the size of a minimum clique modulator.

Authors

• Shubhada Aute
• Fahad Panolan

Keywords

• FPT
• Vertex cover
• Integer quadratic programming