2022/03/13 by Sun‐Yuan Hsieh, Hsieh, Sun-Yuan, Hoàng-Oanh Le +5 · 1 citation
Business, Management and Accounting · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Intellectual Property and Patents
paper · pdf · doi:10.48550/arxiv.2203.06766
openalex publication_date 2022/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let d-claw (or d-star) stand for K1,d, the complete bipartite graph with 1 and d≥ 1 vertices on each part. The d-claw vertex deletion problem, d-CLAW-VD, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1-CLAW-VD and 2-CLAW-VD are just the famous VERTEX COVER problem and the CLUSTER VERTEX DELETION problem, respectively. In this paper, we strengthen a hardness result in [M. Yannakakis, Node-Deletion Problems on Bipartite Graphs, SIAM J. Comput. (1981)], by showing that CLUSTER VERTEX DELETION remains NP-complete when restricted to bipartite graphs of maximum degree 3. Moreover, for every d≥ 3, we show that d-CLAW-VD is NP-complete even when restricted to bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in [F. Bonomo-Braberman et al., Linear-Time Algorithms for Eliminating Claws in Graphs, COCOON 2020], we show that, for every d≥ 3, d-CLAW-VD is NP-complete even when restricted to split graphs without (d+1)-claws, and split graphs of diameter 2. On the positive side, we prove that d-CLAW-VD is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in [Y. Cao et al., Vertex deletion problems on chordal graphs, Theor. Comput. Sci. (2018)] for 2-CLAW-VD on block graphs to d-CLAW-VD for all d≥ 2 and improves the polynomial-time algorithm proposed by F. Bonomo-Brabeman et al. for (unweighted) 3-CLAW-VD on block graphs to 3-block graphs.