As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexi...As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.展开更多
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60673046 and 60673066)the Natural Science Foundation of Liaoning Province (Grant No. 20051082)the Gifted Young Foundation of Dalian University of Technology
文摘As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.
