The Geodetic Hull Number is Hard for Chordal Graphs

Stéphane Bessy 1 Mitre Dourado Lucia Penso Dieter Rautenbach 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Institut für Optimierung und Operations Research
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.
Document type :
Journal articles
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01997429
Contributor : Stéphane Bessy <>
Submitted on : Tuesday, January 29, 2019 - 8:23:43 AM
Last modification on : Friday, December 13, 2019 - 9:32:04 AM

Links full text

arxiv

Identifiers

Collections

LIRMM | CNRS | ALGCO | MIPS | UNIV-MONTPELLIER | TDS-MACS

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

43

Contact

Informations

CCSD