The Geodetic Hull Number is Hard for Chordal Graphs

2017 
Kante 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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    9
    References
    0
    Citations
    NaN
    KQI
    []