Constructive generation of very hard 3-colorability instances |
| |
Authors: | Kazunori Mizuno Seiichi Nishihara |
| |
Institution: | a Department of Computer Science, Takushoku University, Hachioji, Tokyo 193-0985, Japan b Department of Computer Science, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan |
| |
Abstract: | Graph colorability (COL), is a typical constraint satisfaction problem to which phase transition phenomena (PTs), are important in the computational complexity of combinatorial search algorithms. PTs are significant and subtle because, in the PT region, extraordinarily hard problem instances are found, which may require exponential-order computational time to solve. To clarify PT mechanism, many studies have been undertaken to produce very hard instances, many of which were based on generate-and-test approaches. We propose a rather systematic or constructive algorithm that repeats the embedding of 4-critical graphs to arbitrarily generate large extraordinarily hard 3-colorability instances. We demonstrated experimentally that the computational cost to solve our generated instances is of an exponential order of the number of vertices by using a few actual coloring algorithms and constraint satisfaction algorithms. |
| |
Keywords: | Graph coloring Search Phase transition NP-complete Hard problem Heuristics Constraint satisfaction |
本文献已被 ScienceDirect 等数据库收录! |
|