Optimization Online


Integer Programming Formulations for Minimum Deficiency Interval Coloring

Merve Bodur (merve.bodur***at***gatech.edu)
James Luedtke (jim.luedtke***at***wisc.edu)

Abstract: A proper edge-coloring of a given undirected graph with natural numbers identified with colors is an interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edge-coloring and the problem of deciding whether a graph is interval colorable is NP-complete. For a graph that is not interval colorable, determining a graph invariant called the (minimum) deficiency is a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring and can be described as the minimum number of pendant edges whose attachment makes the graph interval colorable. The majority of the studies in the literature either derive bounds on the deficiency of general graphs, or calculate the deficiency of graphs belonging to some special graph classes. In this work, we formulate the Minimum Deficiency Problem, to find the exact deficiency value for any given graph, as an integer program, and further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via a branch-and-cut algorithm. Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach.

Keywords: Interval (consecutive) edge-coloring; minimum deficiency problem; integer programming; cutting planes; column generation

Category 1: Integer Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 07/21/2016
Entry Accepted: 07/21/2016
Entry Last Modified: 08/18/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society