Polyhedral Approach to Total Matching and Total Coloring Problems

A total matching of a graph G = (V, E) is a subset of G such that its elements, i.e. vertices and edges, are pairwise not adjacent. In this context, the Total Matching Problem calls for a total matching of maximum size. This problem has been mainly studied in the literature from a graph theoretical point of view. However, due to the strong connection with well-known combinatorial problems of the Stable Set Problem and the Matching Problem, we focus on an integer programming point of view. In this Thesis, we present a polyhedral approach to the Total Matching Problem, and hence, we introduce the corresponding polytope, namely the Total Matching Polytope. To the best of our knowledge, we are the first to tackle the problem from a polyhedral perspective. We introduce several families of valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, even-clique inequalities induced by complete subgraphs of even order, and, balanced and non-balanced lifted biclique inequalities based on complete bipartite graphs, where the balanced family has the partition of the vertex sets of equal-size, whereas for the second class each vertex partition has different size. We prove that congruent-2k3 cycle inequalities are facet-defining when k = 4, and for cubic graphs, under certain conditions. The non-balanced lifted biclique inequalities are obtained by a lifting procedure and are facet-defining for bipartite graphs. While the vertex-clique, even-clique, and balanced biclique inequalities are always facet-defining. In addition, we provide a first linear complete description for Trees and Complete Bipartite Graphs. For the latter family, the complete characterization is obtained by projecting a higher-dimension polytope onto the original space. This leads to also give an extended formulation of small size for the Total Matching Polytope of Complete Bipartite Graphs. Another problem related to the Total Matching Problem is the Total Coloring Problem. Any partition of the elements into total matchings induces a coloring of G, that is, each total matching is assigned to a color class. Hence, a total coloring is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the endpoints and the edge itself receive different colors. In this Thesis, we propose Integer Linear Programming models for Total Coloring problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Finally, we present computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem.

Un matching totale di un grafo G = (V,E) è un sottoinsieme di G tale che i suoi elementi, cioè vertici e spigoli, sono a coppie non adiacenti. In questo contesto, il Total Matching Problem richiede di trovare un matching totale di dimensione massima. Questo problema è stato principalmente studiato in letteratura da un punto di vista della teoria dei grafi. Tuttavia, a causa del forte collegamento con noti problemi combinatorici dello Stable Set Problem e del Matching Problem, il problema viene trattato da un punto di vista tipico della programmazione intera. In questa Tesi, viene presentato un approccio poliedrale al Total Matching Problem, e quindi, si introduce il corrispondente politopo, ovvero il Total Matching Polytope. Al meglio della nostra conoscenza, tale problema non è stato ancora affrontato da una prospettiva poliedrale. Vengono introdotte diverse famiglie di disuguaglianze valide: disuguaglianze vertex-clique basate su disuguaglianze di clique del politopo dell'insieme stabile, disuguaglianze di cicli congruent-2k3 cycles basate sulla parità dell'insieme dei vertici indotte dal ciclo, disuguaglianze even-clique indotte da sottografi completi di ordine pari e, balanced e non lifted balanced disuguaglianze bicliques basate su grafi bipartiti completi, dove la famiglia bilanciata ha la partizione degli insiemi di vertici di uguale dimensione, mentre la seconda classe ha ogni partizione di vertice di dimensioni diverse. Si dimostra che le disuguaglianze di ciclo congruent-2k3 sono faccette quando k = 4, e per grafi cubici, in determinate condizioni. Le non balanced lifted biclique disuguaglianze sono ottenute mediante una procedura di lifting e definiscono le faccette per grafi bipartiti. Mentre le clique di vertice, le even clique e le balanced bicliques definiscono sempre  faccette. Inoltre, una prima descrizione lineare completa viene fornita per alberi e grafi bipartiti completi. Per quest'ultima famiglia, la caratterizzazione completa si ottiene proiettando un politopo di dimensione superiore nello spazio originario. Ciò porta a dare anche una formulazione estesa di piccola dimensione per il Total Matching Politopo di grafi bipartiti completi. Un altro problema correlato al Total Matching Problem è il Total Coloring Problem. Qualsiasi partizione degli elementi in matching totali induce una colorazione di G, ovvero, ad ogni matching totale viene assegnato una classe di colore. Quindi, una colorazione totale è un'assegnazione di colori a vertici e spigoli tale che né due vertici adiacenti né due spigoli incidenti hanno lo stesso colore e, per ogni spigolo, le estremità e lo spigolo stesso devono ricevere colori diversi.In questa Tesi si propongono modelli di Programmazione Lineare Intera per problemi di Colorazione Totale, e viene studiata la forza del corrispondente rilassamento lineare continuo. La colorazione totale è formulata come il problema di trovare il numero minimo di matching totali che coprano tutti gli elementi del grafo. Questa formulazione di copertura può essere risolta da un algoritmo di generazione di colonne, dove il sottoproblema corrisponde al problema di matching totale pesato. Infine, vengono presentati risultati computazionali di un algoritmo di generazione di colonne per il Total Coloring Problem e di piani di taglio per il problema del Total Matching.