Minimum sum vertex cover : difficulty of ordering

Abstract

Aminimum sum vertex cover of a graph is a vertex cover associated with a permutation of its vertices that minimizes the total cost of covering all edges. The cost of an edge is defined by the smaller index of its two endpoints in the permutation. While this vertex cover is not necessarily the smallest possible, we show that its size, denoted as 𝑘, is polynomially bounded by the size of the minimum vertex covers. We note that finding an optimal ordering is NP-hard even when the vertex set of an optimal solution is given. We propose an 𝑂(𝑚+2𝑘𝑘!𝑘3)-time algorithm for finding aminimum sum vertex cover, where 𝑚 is the size of the input graph, toward which we also show a(𝑘2 +2𝑘)-vertex kernel.