Logo image
Sign in
The Geodetic Hull Number is Hard for Chordal Graphs
Journal article   Peer reviewed

The Geodetic Hull Number is Hard for Chordal Graphs

Stéphane Bessy, Mitre Dourado, Lucia Penso and Dieter Rautenbach
SIAM Journal on Discrete Mathematics, Vol.32(1), pp.543-547
01/2018

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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image