{"ID":2871470,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11448","arxiv_id":"2509.11448","title":"Triangle-Covered Graphs: Algorithms, Complexity, and Structure","abstract":"The widely studied edge modification problems ask how to minimally alter a graph to satisfy certain structural properties. In this paper, we introduce and study a new edge modification problem centered around transforming a given graph into a triangle-covered graph (one in which every vertex belongs to at least one triangle). We first present tight lower bounds on the number of edges in any connected triangle-covered graph of order $n$, and then we characterize all connected graphs that attain this minimum edge count. For a graph $G$, we define the notion of a $Δ$-completion set as a set of non-edges of $G$ whose addition to $G$ results in a triangle-covered graph. We prove that the decision problem of finding a $Δ$-completion set of size at most $t\\geq0$ is $\\mathbb{NP}$-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains $\\mathbb{NP}$-complete even when the input is restricted to connected bipartite graphs. We then study the problem from an algorithmic perspective, providing tight bounds on the minimum $Δ$-completion set size for several graph classes, including trees, chordal graphs, and cactus graphs. Furthermore, we show that the triangle-covered problem admits an $(\\ln n +1)$-approximation algorithm for general graphs. For trees and chordal graphs, we design algorithms that compute minimum $Δ$-completion sets. Finally, we show that the threshold for a random graph $\\mathbb{G}(n, p)$ to be triangle-covered occurs at $n^{-2/3}$.","short_abstract":"The widely studied edge modification problems ask how to minimally alter a graph to satisfy certain structural properties. In this paper, we introduce and study a new edge modification problem centered around transforming a given graph into a triangle-covered graph (one in which every vertex belongs to at least one tri...","url_abs":"https://arxiv.org/abs/2509.11448","url_pdf":"https://arxiv.org/pdf/2509.11448v1","authors":"[\"Amirali Madani\",\"Anil Maheshwari\",\"Babak Miraftab\",\"Paweł Żyliński\"]","published":"2025-09-14T21:45:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}