An O(pn + 1.151p) 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 ¿ V such that the profit, É' — 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.150964p). 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 . We combine our algorithm for p-Profit e¿E' 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. This research is supported by a UVic research grant and by NSERC grant 54194. All graphs considered in this article are simple and undirected.