EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2180. Pareto optimality in graphs: circulations and colorings

Invited abstract in session WD-29: Optimization issues on graphs II (Contributed), stream Combinatorial Optimization.

Wednesday, 14:30-16:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Yiannis Mourtos
Management Science & Technology, Athens University of Economics & Business
2. Pavlos Eirinakis
Industrial Management and Technology, University of Piraeus
3. Michalis Samaris
Department of Science & Technology, Athens University of Economics and Business

Abstract

Motivated by the growing literature on Pareto-optimal matchings, we examine two fundamental graph problems considering that vertices of a graph have preferences. The first is the circulation problem, in which every vertex sends an amount of flow equal to the one it receives; here each vertex has strict and transitive preferences over its out-going arcs, i.e., over the vertices it sends its flow. The second is the list coloring problem where each vertex has preferences over its available colors. Both problems admit an elegant characterization of the Pareto-optimal solutions, i.e., solutions in which no vertex can receive a better stake (i.e., flow or color) without some other vertex receiving a worse one. Well-known mechanisms, namely Top Trading Cycles or Serial Dictatorship, can find a Pareto-optimal circulation or coloring, respectively. Interestingly, although recognizing Pareto-optimality is easy for circulations, it becomes coNP-complete for colorings. We discuss further hard optimization problems for both settings, along with special cases that defy hardness by restricting the structure of either the graph or the preferences of its vertices. We also present several motivating applications, review relevant literature, and propose open issues for future work.

Keywords

Status: accepted

Back to the list of papers