Strong total cover problem links graph sets and matching complexity
The Strong Total Cover Problem
Discrete MathematicsComputational Complexity
Summary
The paper studies a new problem on graphs where one must pick the smallest set of nodes or edges to cover everything in the graph. Vertices cover themselves and their edges, while edges cover themselves and their endpoints. The authors show this problem is difficult to solve in general, similar to some well-known problems, but find some simpler cases where it can be solved efficiently. They also develop approximation methods and characterize geometric structures related to the problem, providing insights that could help design better algorithms.
What this means in practice
- •For network designers: Optimize network monitoring by selecting minimal nodes or links that cover all elements, improving resource use when monitoring communication or power grids.
- •For supply chain managers: Plan minimal control points in distribution networks that cover all routes and nodes to enhance oversight and reduce costs.
Authors
Manuel Aprile, Luca Ferrarini
Abstract
The Strong Total Cover Problem (STCP) is a novel covering problem defined on a graph $G = (V, E)$, where the objective is to find a minimum-cardinality subset $T \subseteq V \cup E$ such that every element of $V \cup E$ is covered. In this setting, a vertex covers itself and all its incident edges, while an edge covers itself together with its two endpoints. The STCP resembles classical covering problems such as Vertex Cover and Edge Cover problems, and naturally arises as the dual of the total matching problem. In this paper, we investigate the STCP from algorithmic, complexity, and polyhedral perspectives. We first establish close connections between STCP, the Dominating Set Problem, and the Maximum Induced Matching Problem. These relationships provide structural insights, imply the NP-hardness of STCP, and identify graph classes for which the problem is polynomial-time solvable. We then investigate the weighted version of STCP, showing that it remains NP-hard even on complete graphs with binary weights. On the other hand, we present a 2-approximation algorithm, and a polynomial-time algorithm for complete bipartite graphs. On the polyhedral side, we introduce the Strong Total Cover Polytope and derive several families of valid inequalities, some of which are shown to define facets. Finally, we provide a complete linear description of the associated polytope for triangular cactus graphs, revealing an interesting contrast with the considerably more intricate facial structure of the dominating set polytope on cactus graphs.