Answers are grounded in this paper and cite their sources.
New edge modification problem transforms graphs into triangle-covered graphs, revealing NP-completeness and algorithm designs.
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≥0 is NP-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains 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 G(n, p) to be triangle-covered occurs at n-2/3.
No takes yet. Share an insight, caveat, or question.
Madani et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: