Facets based on cycles and cliques for the acyclic coloring polytope

Abstract

A coloring of a graph is an assignment of colors to its vertices such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring is a coloring such that no cycle receives exactly two colors, and the acyclic chromatic number ?A(G) of a graph G is the minimum number of colors in any such coloring of G. Given a graph G and an integer k, determining whether ?A(G) ? k or not is NP-complete even for k = 3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In a previous work we presented facet-inducing families of valid inequalities based on induced even cycles for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we continue with this study by introducing new families of facet-inducing inequalities based on combinations of even cycles and cliques.

La coloración de un gráfico es una asignación de colores a sus vértices de modo que dos vértices cualesquiera reciban colores distintos siempre que sean adyacentes. Una coloración acíclica es una coloración tal que ningún ciclo recibe exactamente dos colores, y el número cromático acíclico ?A(G) de un gráfico G es el número mínimo de colores en cualquier coloración de G. Dado un gráfico G y un entero k, determinar si ?A(G) ? k o no es NP-completo incluso para k = 3. El problema de la coloración acíclica surge en el contexto de cálculos eficientes de matrices de Hesse dispersas y simétricas mediante sustitución métodos. En un trabajo anterior presentamos familias de desigualdades válidas inductoras de facetas basadas en ciclos pares inducidos para el politopo asociado a una formulación de programación entera del problema de coloración acíclica. En este trabajo continuamos con este estudio introduciendo nuevas familias de desigualdades inductoras de facetas basadas en combinaciones de ciclos pares y camarillas.

A coloração de um grafo é uma atribuição de cores aos seus vértices de forma que quaisquer dois vértices recebam cores distintas sempre que forem adjacentes. Uma coloração acíclica é uma coloração tal que nenhum ciclo recebe exatamente duas cores, e o número cromático acíclico ?A(G) de um grafo G é o número mínimo de cores em qualquer coloração de G. Dado um grafo G e um inteiro k, determinar se ?A(G) ? k ou não é NP-completo mesmo para k = 3. O problema de coloração acíclica surge no contexto de cálculos eficientes de matrizes Hessianas esparsas e simétricas por meio de métodos de substituição. Em um trabalho anterior apresentamos famílias indutoras de facetas de desigualdades válidas baseadas em ciclos pares induzidos para o politopo associadas a uma formulação de programação inteira do problema de coloração acíclica. Neste trabalho continuamos com este estudo introduzindo novas famílias de desigualdades indutoras de facetas baseadas em combinações de ciclos pares e cliques.