Investigation of Satisfiability Based Solution Approach for Graph Coloring Problem
Prakash C. Sharma1, Narendra S. Chaudhari2
1Prakash C. Sharma, Department of Computer Science & Engineering,Indian Institute of Technology, Indore (M.P.), India.
2Narendra S. Chaudhari, Department of Computer Science & Engineering, Indian Institute of Technology, Indore (M.P.), India.
Manuscript received on 10 October 2016 | Revised Manuscript received on 18 October 2016 | Manuscript Published on 30 October 2016 | PP: 106-112 | Volume-6 Issue-1, October 2016 | Retrieval Number: A4711106116/16©BEIESP
Open Access | Editorial and Publishing Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Graph k-colorability (for k ≥ 3) problem (GCP) is a well-known NP-Complete problem. There are many approaches proposed to solve graph coloring problem till date. There is an alternative approach to solve it efficiently by Satisfiability which is first known NP-Complete problem. We can reduce any NPcomplete problem to/from SAT. Reduction from graph kcolorability problem to satisfiability is an important concept to solve it using efficient SAT solver. In this paper, we are presenting a polynomial 3-SAT encoding technique for k colorable graph. Our formulation generates total (((k-2)*|V| ) + (k*|E|) ) clauses in 3-CNF for k-colorable graph. We tested our encoding formulation approach on different graph coloring instances of DIMACS[8][9] and then investigated the solution of graph coloring problem as a decision problem based on SAT approach using powerful SAT solver Minisat 2.2.
Keywords: 3-Sat, Cnf, Dnf, Graph Coloring, Np-Complete, K-Colorable, Chromatic Number, Dimacs.
Scope of the Article: Problem Solving and Planning