2025/09/14 by Amirali Madani, Madani, Amirali, Anil Maheshwari +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2509.11448
openalex publication_date 2025/09/14 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
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 \mathbbNP-complete and does not admit a constant-factor approximation algorithm under standard complexity assumptions. Moreover, we show that this problem remains \mathbbNP-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 \mathbbG(n, p) to be triangle-covered occurs at n-2/3.