期刊
INFORMATION PROCESSING LETTERS
卷 87, 期 1, 页码 7-12出版社
ELSEVIER
DOI: 10.1016/S0020-0190(03)00229-1
关键词
computational complexity; graph colorability; completeness; Boolean hierarchy
Let M-k be a given set of k integers. Define Exact-M-k-Colorability to be the problem of determining whether or not chi(G), the chromatic number of a given graph G, equals one of the k elements of the set M-k exactly. In 1987, Wagner [Theoret. Comput. Sci. 51 (1987) 53-80] proved that Exact-Mk-Colorability is BH2k (NP)-complete, where M-k = {6k + 1, 6k + 3,...,8k - 1} and BH2k (NP) is the 2kth level of the Boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not chi(G) = 7, where DP = BH2 (NP). Wagner raised the question of how small the numbers in a k-element set M-k can be chosen such that Exact-Mk-Colorability still is BH2k (NP) -complete. In particular. for k = 1. he asked if it is DP-complete to determine whether or not chi(G) = 4. In this note, we solve Wagner's question and prove the optimal result: For each k greater than or equal to 1, Exact-M-k-Colorability is BH2k (NP)-complete for M-k = {3k + 1, 3k + 3,...,5k - 1}. In particular, for k = 1, we determine the precise threshold of the parameter t is an element of {4. 5. 6. 7} for which the problem Exact-{t}-Colorability jumps from NP to DP-completeness: It is DP-complete to determine whether or not chi(G) = 4, yet Exact-(3)-Colorability is in NP. (C) 2003 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据