On the g-centroidal problem in special classes of perfect graphs (Q2713658)

For a connected graph \(G=(V,E)\), the g-centroid is the set of vertices \(v\in V\) for which the number \(w(v)\) attains the minimum value \(\text{gc}(G)\); \(w(v)\) is the maximum size of a g-convex subset \(X\subset V\), \(v\not \in X\). g-convexity of a set means that with its every two vertices \(u\) and \(v\) it contains every shortest \(u\)-\(v\) path. The authors prove that to find the g-centroid or the number \(\text{gc}(G)\) is in general NP-hard. They give polynomial algorithms finding g-centroids for three classes of graphs: maximal outerplanar graphs, split graphs, and Ptolemaic graphs, the complexities being \(O(n^2)\), \(O(m+n\log n)\), and \(O(m^2)\), respectively.