Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs. Définition Mentionnée sans précision supplémentaire, l'expression « coloration des arêtes d'un graphe » désigne le fait d'attribuer à chaque arête une couleur, de sorte que deux arêtes adjacentes (c'est-à-dire ayant une extrémité commune) n'aient jamais la même couleur. (C'est une notion duale de celle de coloration des sommets d'un graphe.) Le nombre minimal de couleurs nécessaire pour réaliser la coloration des arêtes d'un graphe G

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delta - 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Delta = O(log n), and they conjectured the existence of online algorithms using Delta (1+o(1)) colors for Delta = omega(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Delta-edge-coloring algorithm for Delta = omega(log n) known a priori. Surprisingly, if Delta is not known ahead of time, we show that no (e/e-1 - Omega(1)) Delta-edge-coloring algorithm exists. We then provide an optimal, (e/e-1 + o(1))Delta-edge-coloring algorithm for unknown Delta = omega(log n). To obtain our results, we study a nonstandard fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

IEEE COMPUTER SOC2019

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algorithm only knows the distribution from which the edges are sampled.In the query-commit model, the algorithm must query edges to know if they exist and is committed to adding all queried edges that exist to its output.In the price-of-information model, the algorithm incurs costs for querying edges, and the total query cost is subtracted from the output matching's weight.For maximum weighted matching in these models, previously known best algorithms were greedy algorithms that achieve 1/2 approximations. We improve the approximation ratio to 1 - 1/e in both models. Next, we consider situations where the input graphs do not fit into the space available for an algorithm instance. We consider two such models: the semi-streaming model where the algorithm receives the input as a stream of edges and the algorithm has only sub-linear (in the number of edges) space, and the massively parallel computation (MPC) model where the input is distributed among several machines, each of which has sub-linear space, and algorithm instances running on different machines must communicate in synchronous rounds.We start with a particular case of the semi-streaming model where the edges arrive in uniformly random order, and the algorithm goes over the stream only once. For this setting, we give the first algorithm that finds a (1/2 + c)-approximate maximum weighted matching in expectation; such algorithms were previously known only for the unweighted graphs.We then show how to efficiently find (1 - epsilon)-approximate weighted matchings for any epsilon > 0 in multi-pass semi-streaming and MPC models by extending our algorithmic ideas used in the single-pass semi-streaming model with random order edge arrivals.Finally, we study online algorithms for matching, where the input graph is gradually revealed over time. In the online edge-arrival setting, the graph is revealed one edge at a time, and an algorithm is forced to make irrevocable decisions on whether to add each edge to the output matching upon their arrival. We show that no online algorithm can achieve a competitive ratio of 1/2 + c for any constant c > 0 in this setting.In the online vertex-arrival setting, the graph is revealed one vertex at a time, together with its incident edges to already revealed vertices, and the algorithm must irrevocably decide to ignore the revealed vertex or match it to one of the available neighbors.In this setting, we show how to round a previously known fractional online matching algorithm to get an integral online matching algorithm with a competitive ratio of 1/2 + c for some constant c > 0.

EPFL2021

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

EPFL2021