Abstract
Graph colorability (COL) is a constraint satisfaction problem, which has been studied in the context of computational complexity and combinatorial search algorithms. It is also interesting as subjects of heuristics[2]. Many research reports discuss the complexity of COL [2,3,4,8,9,10]. Examples of possible candidates of order parameters that explain the mechanism making COLs very hard include the 3-paths[10], the minimal unsolvable subproblems[8], and the frozen developments[4]. Instead of generate-and-test approaches, we propose a constructive approach producing 3-colorablity problems (3COLs) that are exceptionally hard for usual backtracking algorithms adopting Brélaz heuristics and for Smallk coloring program[1]. Instances generated by our procedure (1) are 4-critical, (2) include no near-4-cliques(n4c’s; 4-cliques with 1 edge removed) as subgraphs, and (3) have the degree of every node limited to 3 or 4: quasi-regular.
This research was supported in part by the Ministry of Education, Culture, Sports, Science and Technology of Japan, Grant-in-Aid for Scientific Research (B)(2), No. 14380134, 2002–2005.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Overview of the Smallk Graph Coloring Program (2000), http://www.cs.ualberta.ca/joe/Coloring/Colorsrc/smallk.html
Brélaz, D.: New Methods to Color the Vertices of a Graph. Comm. ACM 22(4) (1979)
Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where Really Hard Problems Are. In: Proc. 12th IJCAI (1991)
Culberson, J., Gent, I.: Frozen development in graph coloring. Theor. Computer Sci. 265 (2001)
Grant, S.A., Smith, B.M.: Modelling Exceptionally Hard Constraint Satisfaction Problems. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330. Springer, Heidelberg (1997)
Hanson, D., Robinson, G.C., Toft, B.: Remarks on the Graph Colour Theorem of Hajós. Congressus Numerantium, 55 (1986)
Hogg, T., Williams, C.P.: The hardest constraint problems: a double phase transition. Artif. Inell. 69 (1994)
Mammen, D.L., Hogg, T.: A New Look at Easy-Hard-Easy Pattern of Combinatorial Search Difficulty. Jour. Artif. Intell. Research 7 (1997)
Mizuno, K., Nishihara, S.: Toward Ordered Generation of Exceptionally Hard Instances for Graph 3-Colorability. In: Computational Symposium on Graph Coloring and its Generalizations(COLOR 2002), Ithaca, N.Y. (September 2002)
Vlasie, D.R.: Systematic Generation of Very Hard Cases for Graph 3-Colorability. In: Proc. 7th IEEE ICTAI (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nishihara, S., Mizuno, K., Nishihara, K. (2003). A Composition Algorithm for Very Hard Graph 3-Colorability Instances. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_78
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_78
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive