Metraipolis › archive › dc_c0bd2cb389bc

The Strong Total Cover Problem — arXiv:2610.23312

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.23312
License (as archived): CC0-1.0
Archived: 2026-10-19T09:39:33.802Z
SHA-256 of the archived text: 0a5401383cae948b2b14b5e0517532b415dc3207a931b495d483c2430c6d2cdb
Stable URL of this page: https://metraipolis.com/documento/dc_c0bd2cb389bc

How to cite

The Strong Total Cover Problem — arXiv:2610.23312 — arXiv (en), https://arxiv.org/abs/2610.23312 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c0bd2cb389bc (Metraipolis archive dc_c0bd2cb389bc, sha256 0a5401383cae948b2b14b5e0517532b415dc3207a931b495d483c2430c6d2cdb)

BibTeX

@misc{dcc0bd2cb389bc,
  title = {The Strong Total Cover Problem — arXiv:2610.23312},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.23312},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c0bd2cb389bc; sha256 0a5401383cae948b2b14b5e0517532b415dc3207a931b495d483c2430c6d2cdb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23312. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.23312 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:34:59.768Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).