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