Algorithmic aspects of majority domination (Q1371054)

The majority dominating function of a graph \(G\) is a function \(g: V(G)\to\{-1,1\}\) such that for at least half of the vertices \(v\) of \(G\) the sum of values of \(g\) over the closed neighbourhood of \(v\) is at least 1. The minimum value of the sum of values of \(g\) taken over all majority dominating functions of \(G\) is the majority domination number of \(G\). The paper studies the algorithmic complexity of finding the majority domination number for trees, cographs and \(k\)-trees. Cographs are defined in such a way that \(K_1\) is a cograph and for cographs \(G\) and \(H\) also \(G\cup H\) and \(G\times H\) are cographs. (Probably, here the symbols \(\cup\) and \(\times\) denote other operations than disjoint union and Cartesian product, because otherwise cographs would be only graphs without edges.) The \(k\)-trees are defined so that \(K_k\) is a \(k\)-tree and any graph obtained from a \(k\)-tree by adding a new vertex and joining it with all vertices of a \(k\)-clique is again a \(k\)-tree. It is proved that there is an \(O(n^2)\)-time algorithm for computing the majority domination number for a tree, an \(O(n^3)\)-time algorithm for a cograph and a polynomial-time algorithm for a \(k\)-tree, where \(n\) is the number of vertices.