A degree reduction method for an efficient QUBO formulation for the graph coloring problem

We introduce a new degree reduction method for homogeneous symmetric polynomials on binary variables that generalizes the conventional degree reduction methods on monomials introduced by Freedman and Ishikawa. We also design an degree reduction algorithm for general polynomials on binary variables,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-11
Main Authors: Hong, Namho, Jung, Hyunwoo, Kang, Hyosang, Lim, Hyunjin, Seol, Chaehwan, Um, Seokhyun
Format: Article
Language:English
Subjects:
Algorithms
Degree reduction
Graph coloring
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a new degree reduction method for homogeneous symmetric polynomials on binary variables that generalizes the conventional degree reduction methods on monomials introduced by Freedman and Ishikawa. We also design an degree reduction algorithm for general polynomials on binary variables, simulated on the graph coloring problem for random graphs, and compared the results with the conventional methods. The simulated results show that our new method produces reduced quadratic polynomials that contains less variables than the reduced quadratic polynomials produced by the conventional methods.
ISSN:2331-8422