## Contributed Session Thu.1.H 2013

#### Thursday, 10:30 - 12:00 h, Room: H 2013

**Cluster 11: Integer & mixed-integer programming** [...]

### Polyhedral combinatorics

**Chair: Vinicius Leal do Forte**

**Thursday, 10:30 - 10:55 h, Room: H 2013, Talk 1**

**Diego Delle Donne**

Vertex coloring polytopes over trees and block graphs

**Coauthor: Javier L. Marenco**

**Abstract:**

Many variants of the vertex coloring problem have been defined, such as *precoloring extension*, *\mu*-coloring, *(** γ , \mu*)-coloring, and *list coloring*. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which some of these problems can be solved in polynomial time. The standard integer programming model for coloring problems uses a binary variable *x*_{vc} for each vertex *v* and each color *c* to indicate whether *v* is assigned *c* or not. An extension of this model considers binary variables *w*_{c} for each color *c* to indicate whether color *c* is used or not. In this work we study this formulation for the polynomial cases of the coloring problems mentioned above. In particular, we prove that if the classical vertex coloring problem yields an integer polytope for a family of graphs, then the same holds for *\mu*-coloring, (* γ , \mu*)-coloring, and list coloring over the same family. We prove that the polytope associated to these problems over trees is integer, and we provide empirical evidence suggesting that the same holds for block graphs.

**Thursday, 11:00 - 11:25 h, Room: H 2013, Talk 2**

**Vinicius Leal do Forte**

Formulations and exact solution algorithms for the minimum two-connected dominating set problem

**Coauthors: Abilio Lucena, Nelson Maculan**

**Abstract:**

Given an undirected graph *G=(V,E)* a dominating set is a subset *D* of *V* such that any vertex of *V* is in *D* or has a neighbor vertex in *D*. The dominating set is *2*-connected if the subgraph *G(D)*, it induces in *G*, is *2*-connected and the Minimum *2*-Connected Dominating Set Problem (M2CDSP) asks for a least cardinality *2*-connected *D*. The problem has applications in the design of ad-hoc wireless telecommunication networks. However no exact solution algorithm or heuristic appears to exist for it in the literature. In this presentation we discuss a number of different formulations for the M2CDSP as well as some valid inequalities to strengthen them. The formulations address the two variants of the problem, namely the *2*-edge connected and the *2*-node connected ones and are based on either cut-set inequalities or multi-commodity flows. Preliminary computational results are discussed for branch and cut algorithms based on these formulations.