The Strong Total Cover Problem
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 ⊆ V ∪ E such that every element of V ∪ 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.
Related
- A proof of the strong Erdős--Frankl--Füredi cover-free conjecture
- Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
- Balanced Support Calibrations for Moser's Worm Problem: Exact Certificate and Bound of Triangular Cover
- Approach to total collision in the spatial 4-body problem
- Solving the Tikhonov Regularization of the Total Least Squares Problem by matrix simultaneous diagonalization via congruence
BibTeX
@misc{aprile2026strong,
title = {{The Strong Total Cover Problem}},
author = {Manuel Aprile and Luca Ferrarini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23312},
eprint = {2610.23312},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23312},
}
RIS
TY - UNPB
TI - The Strong Total Cover Problem
AU - Manuel Aprile
AU - Luca Ferrarini
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23312
UR - https://arxiv.org/abs/2610.23312
AB - 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 ⊆ V ∪ E such that every element of V ∪ 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.
ER -