Computational complexity of the negative decision number of graphs.
Hongyu Liang · Australas. J Comb. · 2012
Let G = (V,E) be a graph. A function f : V → {−1, 1} is called a bad function of G if ∑ u∈NG(v) f(u) ≤ 1 for each v ∈ V , where NG(v) is the set of neighbors of v in G. The negative decision number of G, introduced by Wang, is the maximum value of ∑ v∈V f(v) taken over all bad functions of G. In this paper, we comprehensively study the negative decision number from algorithmic, complexity, and graph-theoretic points of view. Our main results are as follows. 1. We prove that it is NP-hard to compute the negative decision number of a given graph, even if the graph is bipartite. Moreover, it is NP-complete to decide whether the negative decision number of a given bipartite graph is at least k, where k is any fixed integer (not necessarily positive). On the other hand, we show that the negative decision number can be computed in polynomial time for several special classes of graphs including trees. 2. For a below-upper-bound formulation of the problem of computing the negative decision number, we show an asymptotically tight approximation threshold of Θ(log |V |). Specifically, it can be approximated within a factor of O(log |V |) in polynomial time, but cannot be approximated better than c log |V | for some constant c > 0 unless NP⊆ DTIME(n log ). 3. The exact values of the negative decision number are determined for complete multipartite graphs, wheels, and fans. ∗ This work was supported in part by the National Basic Research Program of China Grants 2011CBA00300, 2011CBA00301, and the National Natural Science Foundation of China Grants 61033001, 61061130540, 61073174.