More Like this

1. Graph coloring and semidefinite rank

   https://doi.org/10.1007/978-3-031-06901-7_29  

   Mirka, Renee ; Smedira, Devin ; Williamson, David P. ( May 2022 , Lecture notes in computer science)

   Aardal, Karen ; Sanità, Laura (Ed.)

   This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan [10] give a vector program for which a coloring of the graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has sufficiently high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have sufficiently high rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a k-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if the graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank, since it is known that the uniquely colorable planar graphs are precisely the planar 3-trees. We then modify the semidefinite program to have an objective function with costs, and explore when we can create a cost function whose optimal dual solution has sufficiently high rank. We show that it is always possible to construct such a cost function given the graph coloring. The construction of the cost function gives rise to a heuristic for graph coloring which we show works well in the case of planar graphs; we enumerated all maximal planar graphs with a K4 of up to 14 vertices, and the heuristics successfully colored 99.75% of them. Our research was motivated by the Colin de Verdière graph invariant [5] (and a corresponding conjecture of Colin de Verdière), in which matrices that have some similarities to the dual feasible matrices must have high rank in the case that graphs are of a certain type; for instance, planar graphs have rank that would imply the 4-colorability of the primal solution. We explore the connection between the conjecture and the rank of the dual solutions. 

   more » « less
2. Integer programming formulations for minimum deficiency interval coloring

   https://doi.org/10.1002/net.21826  

   Bodur, Merve ; Luedtke, James R. ( June 2018 , Networks)

   A proper edge‐coloring of a given undirected graph with natural numbers identified with colors is aninterval (or consecutive) coloringif 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)deficiencyis a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring. 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 derive integer programming formulations of theMinimum Deficiency Problemwhich seeks to find the exact deficiency value of a graph, given a bound on the number of colors that can be used. We further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via abranch‐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.

    

   more » « less
3. Max cut and semidefinite rank

   https://doi.org/10.1016/j.orl.2024.107067  

   Mirka, Renee ; Williamson, David P ( March 2024 , Operations Research Letters)

   This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n-1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs. 

   more » « less
4. Three coloring via triangle counting

   Hamaker, Zachary ; Vatter, Vincent ( August 2023 , The Australasian journal of combinatorics)

   Albert, Michael ; Billington, Elizabeth J (Ed.)

   In the first partial result toward Steinberg’s now-disproved three coloring conjecture, Abbott and Zhou used a counting argument to show that every planar graph without cycles of lengths 4 through 11 is 3-colorable. Implicit in their proof is a fact about plane graphs: in any plane graph of minimum degree 3, if no two triangles share an edge, then triangles make up strictly fewer than 2/3 of the faces. We show how this result, combined with Kostochka and Yancey’s resolution of Ore’s conjecture for k = 4, implies that every planar graph without cycles of lengths 4 through 8 is 3-colorable. 

   more » « less
5. A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”

   https://doi.org/10.1002/net.21849  

   Validi, Hamidreza ; Buchanan, Austin ( October 2018 , Networks)

   In the article “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” (Networks39(1) (2002), 53‐60), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using onlyO(n) variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (“A zero‐one programming model for contiguous land acquisition.” Geographical Analysis34(4) (2002), 330‐349).

    

   more » « less