2023/06/23 by Sounaka Mishra, Mishra, Sounaka
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2306.13306
openalex publication_date 2023/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For t≥ 3, K1, t is called t-claw. In minimum t-claw deletion problem (Min-t-Claw-Del), given a graph G=(V, E), it is required to find a vertex set S of minimum size such that G[V∖ S] is t-claw free. In a split graph, the vertex set is partitioned into two sets such that one forms a clique and the other forms an independent set. Every t-claw in a split graph has a center vertex in the clique partition. This observation motivates us to consider the minimum one-sided bipartite t-claw deletion problem (Min-t-OSBCD). Given a bipartite graph G=(A ∪ B, E), in Min-t-OSBCD it is asked to find a vertex set S of minimum size such that G[V ∖ S] has no t-claw with the center vertex in A. A primal-dual algorithm approximates Min-t-OSBCD within a factor of t. We prove that it is \UGC-hard to approximate with a factor better than t. We also prove it is approximable within a factor of 2 for dense bipartite graphs. By using these results on Min-t-OSBCD, we prove that Min-t-Claw-Del is \UGC-hard to approximate within a factor better than t, for split graphs. We also consider their complementary maximization problems and prove that they are \APX-complete.