A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem
Prakash C Sharma and Narendra S Chaudhari. Article: A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem. IJCA Special Issue on Optimization and On-chip Communication ooc(1):23-27, February 2012. Full text available. BibTeX
@article{key:article,
author = {Prakash C. Sharma and Narendra S. Chaudhari},
title = {Article: A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem},
journal = {IJCA Special Issue on Optimization and On-chip Communication},
year = {2012},
volume = {ooc},
number = {1},
pages = {23-27},
month = {February},
note = {Full text available}
}
Abstract
The satisfiability problem (SAT) is one of the most prominent problems in theoretical computer science for understanding of the fundamentals of computation. It is first known NP-Complete problem. Graph k-Colorability (for k ? 3) Problem (GCP) is also an well known NP-Complete problem. We can reduce any NP-Complete problem to/from SAT. Reduction from satisfiability problem to graph k-colorability problem or vice versa is an important concept to solve one of the hard scheduling problem, frequency assignment in cellular network. The frequency assignment problem is very similar to the graph k-colorability problem. In this paper, we are presenting a polynomial reduction from any instance of 3-CNF-SAT formula to k-colorable graphs. Moret [2] gave an reduction approach from 3-SAT to 3-colorable graph. According to Moret, reduced 3-colorable graph having (2n + 3m + 1) vertices and (3n + 6m) edges, where n is the number of variables and m is number of clauses contained by 3-SAT formula. Here, we generalized the reduction approach to reduce any instance of 3-CNF-SAT formula to a k-colorable graph in polynomial time with mathematical proof. Our reduction approach generate a k-colorable graph with |V| = (2n + 3m + (k-2)) vertices and |E| = (3n + 6m) edges for k = 3 and |E| = (|E| of (k-1)-colorable graph + (|V|-1)) edges for k >3 corresponding to any instance of 3-CNF-SAT. Further, we give the formulation of graph k-colorability to frequency assignment problem in cellular network.
References
- Alexander Tsiatas, “Phase Transitions in Boolean Satisfiability and Graph Coloring”, May 2008, Department of Computer Science, Cornell University, (www.cseweb.ucsd.edu/users/atsiatas/phase.pdf).
- Bernard M. Moret “The Theory of Computation” Pearson Education, 1998, chapter 7, Proving Problem Hard, pp 226-252
- Garey, M. R. and Johnson, D. S., Computers and Interactability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
- Daniel Marx, “Graph Colouring Problems and their applications in Scheduling”, Periodica Polytechnica Ser El. Eng Vol.48, No.1, pp. 11-16 (2004)
- Maaly A. Hassan and Andrew Chickadel, “A Review Of Interference Reduction In Wireless Networks Using Graph Coloring Methods” , International journal on applications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.3, No.1, March 2011, pp 58-67.
- Mohammad Malkawi, Mohammad Al-Haj Hassan and Osama Al-Haj Hassan, “New Exam Scheduling Algorithm using Graph Coloring”, The International Arab Journal of Information Technology, Vol. 5, No. 1, January 2008, pp 80-87
- Taehoon P. and Lee, C.Y., (1994) “On the k-coloring problem”, Journal of Korean OR/MS Society, 19, pp. 219-233.
- De Werra, D. and Gay, Y., (1994), “Chromatic scheduling and frequency assignment”, Discrete Applied Mathematics 49, pp. 165-174.
- L. Adleman and K. Manders, “Reducibility, randomness and intractability (abstract)”, in STOC 77: Proceedings of the ninth annual ACM symposium on Theory of computing. New York NY, USA: ACM Press, 1977, pp. 151-163.
- S. A. Cook, “The P versus NP problem”, April 2000, Computer Science Department, University of Toronto. http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf.