Hub set problem

Presented by Sheng Long Peng at AAAC 2011

(connnected) Hub number is the size of the smallest (connected) hub set.

Hub set is similar to dominating set.

Split graph, V = C \cup I where C is a clique and I is an independent set.

Dominating set is NP-complete on split graph.

There exist a minimum dominating set D such that D \subseq C. For split graph, dominating set equivalent to connected dominating set. This the hub set and connected hub set is NP-complete on split graph and chordal graph.

Present polynomial algorithms for the following classes of graphs.

Graphs of treewidth at most k. Tree decomposition of a graph, nice tree decomposition.

Interval graph. Connected hub set forms a path, can be found in linear time.

Permutation graph.

Co-graph (P_4-free graph).