The Geodetic Hull Number is Hard for Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles SIAM Journal on Discrete Mathematics Year : 2018

The Geodetic Hull Number is Hard for Chordal Graphs

Stéphane Bessy
Mitre Dourado
  • Function : Author
Lucia Penso
  • Function : Author

Abstract

Kanté and Nourine [SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm for the computation of the hull number of chordal graphs. We point out a gap in the correctness proof of their algorithm for chordal graphs and show that computing the hull number of a chordal graph is NP-hard, which most likely rules out the existence of a polynomial time algorithm.

Dates and versions

lirmm-01997429 , version 1 (29-01-2019)

Identifiers

Cite

Stéphane Bessy, Mitre Dourado, Lucia Penso, Dieter Rautenbach. The Geodetic Hull Number is Hard for Chordal Graphs. SIAM Journal on Discrete Mathematics, 2018, 32 (1), pp.543-547. ⟨10.1137/17M1131726⟩. ⟨lirmm-01997429⟩
56 View
0 Download

Altmetric

Share

More