An O(pn + 1.151~p)-Algorithm for p-Profit Cover and Its Practical Implications for Vertex Cover

摘要

We introduce the problem PROFIT COVER which finds application in, among other areas, psychology of decision-making. A common assumption is that net value is a major determinant of human choice. PROFIT COVER incorporates the notion of net value in its definition. For a given graph G = (V, E) and an integer p > 0, the goal is to determine PC is contained in V such that the profit, |E'| ? |PC|, is at least p, where E' are the by PC covered edges. We show that p-PROFIT COVER is a parameterization of VERTEX COVER. We present a fixed-parameter-tractable (fpt) algorithm for P-PROFIT COVER that runs in O(p|V| + 1.150964~p). The algorithm generalizes to an fpt-algorithm of the same time complexity solving the problem p-EDGE WEIGHTED PROFIT COVER, where each edge e ∈ E has an integer weight w(e) > 0, and the profit is determined by ∑_(e∈E') w(e) - |PC|. We combine our algorithm for p-PROFIT COVER with an fpt-algorithm for k-VERTEX COVER. We show that this results in a more efficient implementation to solve MINIMUM VERTEX COVER than each of the algorithms independently.