EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4163. Polynomial-size Formulation for Edge Coloring Problems on Forests

Invited abstract in session WA-25: Topics in Integer Programming I, stream Combinatorial Optimization.

Wednesday, 8:30-10:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Emiliano Lancini
LAMSADE, Université Paris Dauphine PSL
2. Michele Barbato
Dipartimento di Informatica ``Giovanni degli Antoni'', Università degli Studi di Milano

Abstract

An edge coloring of a graph G is an assignment of colors to the edges so that two incident edges receive distinct colors.
In particular, one is often interested in determining an actual edge coloring with the minimum number of colors so to explicitly assign tasks to machines over time.
In the general case, this problem is known to be NP-Hard, however, if G is bipartite, one can solve this problem efficiently, through constructive algorithms.
One drawback of this ``algorithmic'' approach is that it often involves sophisticated implementation. Moreover, finding edge coloring that minimize a generic objective function on bipartite graph is known to be NP-Hard.

The edge coloring Polytope of a graph G is the convex hull of all the possible edge coloring of G.
In this work, we prove that a natural formulation of the edge coloring polytope on forests is polynomial in size and is described by a totally unimodular matrix. The interest towards this result is twofold. On one hand, it allows to use linear programming techniques to solve edge-coloring problems. On the other, it gives a polynomiality proof for all edge coloring problems on forests.
Our results give an alternative proof to different known results such as the max-edge coloring problem on forests and the minimum-sum edge coloring on forests and multicycles.

Keywords

Status: accepted

Back to the list of papers