.png){kind=icon}
.png){kind=icon}
Return
Triangle-covered graphs: Algorithms, complexity, and structure
.png){kind=icon}
OA
AI
DOI：10.1016/j.tcs.2026.115848.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 Delta-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 Delta-completion set of size at most t >= 0 is NOD-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains NOD-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 Delta-completion set size for several graph classes, including trees, chordal graphs, and cactus graphs. Furthermore, we show that the triangle-covered problem admits an (lnn+ 1)-approximation algorithm for general graphs. For trees and chordal graphs, we design algorithms that compute minimum Delta-completion sets. Finally, we show that the threshold for a random graph G(n, p) to be triangle-covered occurs at n-2/3.
Keywords:
Computational complexity
Graph algorithms
Optimal algorithms
Edge modification problems
Approximation algorithms
Journal
IF:
1
Papers:
248
Citations:
1.0W