TY - JOUR

T1 - On the d-Claw Vertex Deletion Problem

AU - Hsieh, Sun Yuan

AU - Le, Hoang Oanh

AU - Le, Van Bang

AU - Peng, Sheng Lung

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2024/2

Y1 - 2024/2

N2 - 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 recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 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 Cao et al (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 Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs.

AB - 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 recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 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 Cao et al (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 Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs.

UR - http://www.scopus.com/inward/record.url?scp=85164142565&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85164142565&partnerID=8YFLogxK

U2 - 10.1007/s00453-023-01144-w

DO - 10.1007/s00453-023-01144-w

M3 - Article

AN - SCOPUS:85164142565

SN - 0178-4617

VL - 86

SP - 505

EP - 525

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -