On the parameterized complexity of the geodesic hull number

Several recent papers obtained complexity results regarding the geodesic hull number hngd(G) of a graph G. In this paper, we prove that determining whether hngd(G)≤k is W[2]-hard parameterized by k in diameter-two graphs and is W[1]-hard parameterized by tw+k, where tw is the treewidth of G. Despite...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-10, Vol.791, p.10-27
Main Authors: Kanté, Mamadou Moustapha, Marcilon, Thiago, Sampaio, Rudini
Format: Article
Language:English
Subjects:
Geodesic convexity
Hull number
Parameterized complexity
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Several recent papers obtained complexity results regarding the geodesic hull number hngd(G) of a graph G. In this paper, we prove that determining whether hngd(G)≤k is W[2]-hard parameterized by k in diameter-two graphs and is W[1]-hard parameterized by tw+k, where tw is the treewidth of G. Despite this, for graphs with bounded treewidth tw, we prove that hngd(G) is computable in polynomial time O((tw+2)tw+5n2tw+5).
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.05.005