CFP last date
22 April 2024
Reseach Article

A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem

Published on February 2012 by Prakash C. Sharma, Narendra S. Chaudhari
Optimization and On-chip Communication
Foundation of Computer Science USA
OOC - Number 1
February 2012
Authors: Prakash C. Sharma, Narendra S. Chaudhari
d02be292-02c5-4455-a6ac-ac8633848f6b

Prakash C. Sharma, Narendra S. Chaudhari . A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem. Optimization and On-chip Communication. OOC, 1 (February 2012), 23-27.

@article{
author = { Prakash C. Sharma, Narendra S. Chaudhari },
title = { A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem },
journal = { Optimization and On-chip Communication },
issue_date = { February 2012 },
volume = { OOC },
number = { 1 },
month = { February },
year = { 2012 },
issn = 0975-8887,
pages = { 23-27 },
numpages = 5,
url = { /specialissues/ooc/number1/5467-1005/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Special Issue Article
%1 Optimization and On-chip Communication
%A Prakash C. Sharma
%A Narendra S. Chaudhari
%T A New Reduction from 3-SAT to Graph K-Colorability for Frequency Assignment Problem
%J Optimization and On-chip Communication
%@ 0975-8887
%V OOC
%N 1
%P 23-27
%D 2012
%I International Journal of Computer Applications
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
  1. 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).
  2. Bernard M. Moret “The Theory of Computation” Pearson Education, 1998, chapter 7, Proving Problem Hard, pp 226-252
  3. Garey, M. R. and Johnson, D. S., Computers and Interactability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
  4. Daniel Marx, “Graph Colouring Problems and their applications in Scheduling”, Periodica Polytechnica Ser El. Eng Vol.48, No.1, pp. 11-16 (2004)
  5. 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.
  6. 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
  7. Taehoon P. and Lee, C.Y., (1994) “On the k-coloring problem”, Journal of Korean OR/MS Society, 19, pp. 219-233.
  8. De Werra, D. and Gay, Y., (1994), “Chromatic scheduling and frequency assignment”, Discrete Applied Mathematics 49, pp. 165-174.
  9. 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.
  10. 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.
Index Terms

Computer Science
Information Sciences

Keywords

3-SAT CNF graph k-colorability NP-Complete chromatic number frequency assignment