Author name cluster

Jérôme Monnot

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers

2 author rows

JAIR Journal 2025 Journal Article

On a Simple Hedonic Game with Graph-Restricted Communication

Vittorio Bilò
Laurent Gourvès
Jérôme Monnot

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.

PDF Details DOI

TCS Journal 2023 Journal Article

Project games

Vittorio Bilò
Laurent Gourvès
Jérôme Monnot

We consider a strategic game, called project game, where each agent has to choose a project among her own list of available projects. The model includes positive weights expressing the capacity of a given agent to contribute to a given project. The realization of a project produces some reward that has to be allocated to the agents. The reward of a realized project is fully allocated to its contributors according to a simple proportional rule. Existence and computational complexity of pure Nash equilibria is addressed and their efficiency is investigated according to both the utilitarian and the egalitarian social function.

TCS Journal 2022 Journal Article

Complexity and algorithms for constant diameter augmentation problems

Eun Jung Kim
Martin Milanič
Jérôme Monnot
Christophe Picouleau

We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d.

TCS Journal 2022 Journal Article

Extension and its price for the connected vertex cover problem

Mehdi Khosravian Ghadikolaei
Nikolaos Melissinos
Jérôme Monnot
Aris Pagourtzis

We consider extension variants of Vertex Cover and Independent Set, following a line of research initiated in [10]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G = ( V, E ) and a vertex set U ⊆ V, does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S, such that U ⊆ S (respectively, U ⊇ S ). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC, that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE), a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs.

TCS Journal 2022 Journal Article

On the complexity of solution extension of optimization problems

Katrin Casel
Henning Fernau
Mehdi Khosravian Ghadikolaei
Jérôme Monnot
Florian Sikora

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = ( V, E ), one usually arrives at the problem to decide for a vertex set U ⊆ V (pre-solution), if there exists a minimal vertex cover S (i. e. , a vertex cover S ⊆ V such that no proper subset of S is a vertex cover) with U ⊆ S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP -complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP -completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.

TCS Journal 2021 Journal Article

Algorithmic aspects of upper edge domination

Jérôme Monnot
Henning Fernau
David Manlove

We study the problem of finding a minimal edge dominating set of maximum size in a given graph G = ( V, E ), called Upper EDS. We show that this problem is not approximable within a ratio of n ε − 1 2, for any ε ∈ ( 0, 1 2 ), assuming P ≠ NP, where n = | V |. On the other hand, for graphs of minimum degree at least 2, we give an approximation algorithm with ratio 1 n, matching this lower bound. We further show that Upper EDS is APX -complete in bipartite graphs of maximum degree 4, and NP -hard in planar bipartite graphs of maximum degree 4.

TCS Journal 2021 Journal Article

Strong cliques in diamond-free graphs

Nina Chiarelli
Berenice Martínez-Barona
Martin Milanič
Jérôme Monnot
Peter Muršič

A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.

JAAMAS Journal 2020 Journal Article

Computing and testing Pareto optimal committees

Haris Aziz
Jérôme Monnot

Abstract Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. For each of the preference extensions, we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous or linear. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.

TCS Journal 2019 Journal Article

Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs

Kaveh Khoshkhah
Mehdi Khosravian Ghadikolaei
Jérôme Monnot
Dirk Oliver Theis

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results.

TCS Journal 2019 Journal Article

Efficient reallocation under additive and responsive preferences

Haris Aziz
Péter Biró
Jérôme Lang
Julien Lesca
Jérôme Monnot

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. While finding an arbitrary Pareto optimal allocation is generally easy, checking whether a particular allocation is Pareto optimal can be much more difficult. This problem is equivalent to checking that the allocated objects cannot be reallocated in such a way that at least one agent prefers her new allocation to her old one, and no agent prefers her old allocation to her new one. We consider the problem for two related types of preference relations over sets of objects. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over individual objects, and that their underlying preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.

TCS Journal 2019 Journal Article

On maximin share allocations in matroids

Laurent Gourvès
Jérôme Monnot

The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a ( 1 − ε ) -approximation for two agents, and a ( 8 / 9 − ε ) -approximation for three agents. Apart from the extension to matroids, the ( 8 / 9 − ε ) -approximation for three agents improves on a ( 7 / 8 − ε ) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed.

TCS Journal 2018 Journal Article

The many facets of upper domination

Cristina Bazgan
Ljiljana Brankovic
Katrin Casel
Henning Fernau
Klaus Jansen
Kim-Manuel Klein
Michael Lampis
Mathieu Liedloff

This paper studies Upper Domination, i. e. , the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.

TCS Journal 2017 Journal Article

Bi-objective matchings with the triangle inequality

Laurent Gourvès
Jérôme Monnot
Fanny Pascual
Daniel Vanderpooten

This article deals with a bi-objective matching problem. The input is a complete graph and two values on each edge (a weight and a length) which satisfy the triangle inequality. It is unlikely that every instance admits a matching with maximum weight and maximum length at the same time. Therefore, we look for a compromise solution, i. e. a matching that simultaneously approximates the best weight and the best length. For which approximation ratio ρ can we guarantee that any instance admits a ρ-approximate matching? We propose a general method which relies on the existence of an approximate matching in any graph of small size. An algorithm for computing a 1/3-approximate matching in any instance is provided. The algorithm uses an analytical result stating that every instance on at most 6 nodes must admit a 1/2-approximate matching. We extend our analysis with a computer-aided approach for larger graphs, indicating that the general method may produce a 2/5-approximate matching. We conjecture that a 1/2-approximate matching exists in any bi-objective instance satisfying the triangle inequality.

AAMAS Conference 2016 Conference Paper

Optimal Reallocation Under Additive and Ordinal Preferences

Haris Aziz
Péter Biró
Jérôme Lang
Julien Lesca
Jérôme Monnot

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over single objects, and that their preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality. General Terms Economics, Theory and Algorithms

TCS Journal 2015 Journal Article

The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles

Luerbio Faria
Laurent Gourvès
Carlos A. Martinhon
Jérôme Monnot

We introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property π, a c-edge-colored graph G c not satisfying π, and an edge-recoloring cost matrix R = [ r i j ] c × c where r i j ≥ 0 denotes the cost of changing color i of edge e to color j. Basically, in this kind of problem the idea is to change the colors of one or more edges of G c in order to construct a new edge-colored graph such that the total edge-recoloring cost is minimized and property π is satisfied. We also consider the destruction of potentially undesirable structures with the minimum edge-recoloring cost. In this paper, we are especially concerned with the construction and destruction of properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs. Some related problems and future directions are presented.

TCS Journal 2015 Journal Article

Worst case compromises in matroids with applications to the allocation of indivisible goods

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents with additive utilities so as to provide worst case guarantees on agents' utilities. Demko and Hill [6] showed the existence of an allocation where every agent values his share at least V n ( α ), which is a family of nonincreasing functions of α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed in [15]. Interestingly, V n ( α ) is tight for some values of α, i. e. it matches the highest possible utility of the least happy agent. However, this is not true for all values of α. We propose a family of functions W n such that W n ( x ) ≥ V n ( x ) for all x, and W n ( x ) > V n ( x ) for values of x where V n ( x ) is not tight. The functions W n apply on a problem that generalizes the allocation of indivisible goods. It is to find a base in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas. We also present an upper bound on the utility of the least happy agent.

ECAI Conference 2014 Conference Paper

Near Fairness in Matroids

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

This article deals with the fair allocation of indivisible goods and its generalization to matroids. The notions of fairness under consideration are equitability, proportionality and envy-freeness. It is long known that some instances fail to admit a fair allocation. However, an almost fair solution may exist if an appropriate relaxation of the fairness condition is adopted. This article deals with a matroid problem which comprises the allocation of indivisible goods as a special case. It is to find a base of a matroid and to allocate it to a pool of agents. We first adapt the aforementioned fairness concepts to matroids. Next we propose a relaxed notion of fairness said to be near to fairness. Near fairness respects the fairness up to one element. We show that a nearly fair solution always exists and it can be constructed in polynomial time in the general context of matroids.

TCS Journal 2014 Journal Article

On the complexity of the selective graph coloring problem in some special classes of graphs

Marc Demange
Jérôme Monnot
Petrica Pop
Bernard Ries

In this paper, we consider the selective graph coloring problem. Given an integer k ≥ 1 and a graph G = ( V, E ) with a partition V 1, …, V p of V, it consists in deciding whether there exists a set V ∗ in G such that | V ∗ ∩ V i | = 1 for all i ∈ { 1, …, p }, and such that the graph induced by V ∗ is k-colorable. We investigate the complexity status of this problem in various classes of graphs.

IJCAI Conference 2013 Conference Paper

A Matroid Approach to the Worst Case Allocation of Indivisible Goods

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents so as to maximize the utility of the least happy agent. [Demko and Hill, 1988] showed the existence of an allocation where every agent values his share at least Vn(α), which is a family of nonincreasing functions in a parameter α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed [Markakis and Psomas, 2011]. Interestingly, Vn(α) is tight for some values of α, i. e. it is the best lower bound on the valuation of the least happy agent. However, it is not true for all values of α. We propose a family of functions Wn such that Wn(x) ≥ Vn(x) for all x, and Wn(x) > Vn(x) for values of x where Vn(x) is not tight. The new functions Wn apply on a problem which generalizes the allocation of indivisible goods. It is to find a solution (base) in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas.

PDF Details DOI

TCS Journal 2013 Journal Article

Reoptimization of maximum weight induced hereditary subgraph problems

Nicolas Boria
Jérôme Monnot
Vangelis Th. Paschos

The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I ′ resulting from a local modification of I that consists of insertions or removals of a small number of data, we wish to use OPT in order to solve Π in I ′. The aim is to achieve either a better approximation ratio or a better running time (or both) than guaranteed by ex nihilo computation. We use this setting in order to study weighted versions of several representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. The main problems studied are max independent set, max k -colorable subgraph and max split subgraph under vertex insertions and deletions.

TCS Journal 2013 Journal Article

Single approximation for the biobjective Max TSP

Cristina Bazgan
Laurent Gourvès
Jérôme Monnot
Fanny Pascual

We mainly study the Max TSP with two objective functions. We propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analyzed in three cases. When both (respectively, at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 5 12 − ε ≈ 0. 41 (respectively, 3 8 − ε ). When the triangle inequality is not assumed on any objective function, the algorithm is 1 + 2 2 14 − ε ≈ 0. 27 -approximate.

ECAI Conference 2012 Conference Paper

Approximate Tradeoffs on Matroids

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

We consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents an agent's utility. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then, a natural aim is to find tradeoffs. We investigate tradeoff solutions with guarantees for the agents. The focus is on discrete problems having a matroid structure. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.

JAAMAS Journal 2012 Journal Article

Fair solutions for some multiagent optimization problems

Bruno Escoffier
Laurent Gourvès
Jérôme Monnot

Abstract We consider optimization problems in a multiagent setting where a solution is evaluated with a vector. Each coordinate of this vector represents an agent’s utility for the solution. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for all agents. Then, a natural aim is to find solutions that maximize the satisfaction of the least satisfied agent, where the satisfaction of an agent is defined as his relative utility, i. e. , the ratio between his utility for the given solution and his maximum possible utility. This criterion captures a classical notion of fairness since it focuses on the agent with lowest relative utility. We study worst-case bounds on this ratio: for which ratio a feasible solution is guaranteed to exist, i. e. , to what extend can we find a solution that satisfies all agents? How can we build these solutions in polynomial time? For several optimization problems, we give polynomial-time deterministic algorithms which (almost always) achieve the best possible ratio.

TARK Conference 2011 Conference Paper

Compilation and communication protocols for voting rules with a dynamic set of candidates

Yann Chevaleyre
Jérôme Lang
Nicolas Maudet
Jérôme Monnot

We address the problem of designing communication protocols for voting rules when the set of candidates can evolve via the addition of new candidates. We show that the necessary amount of communication that must be transmitted between the voters and the central authority depends on the amount of space devoted to the storage of the votes over the initial set of candidates. This calls for a bicriteria evaluation of protocols. We consider a few usual voting rules, and three types of storage functions: full storage, where the full votes on the initial set of voters are stored; null storage, where nothing is stored; and anonymous storage, which lies in-between. For some of these pairs (voting rule, type of storage) we design protocols and show that they are asymptotically optimal by determining the communication complexity of the rule under the storage function considered.

AAAI Conference 2010 Conference Paper

Possible Winners when New Candidates Are Added: The Case of Scoring Rules

Yann Chevaleyre
Jérôme Lang
Nicolas Maudet
Jérôme Monnot

In some voting situations, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number k of new candidates will be added. Focusing on scoring rules, we give complexity results for the above possible winner problem.

TCS Journal 2008 Journal Article

A better differential approximation ratio for symmetric TSP

Bruno Escoffier
Jérôme Monnot

In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3 / 4 − ε (for any ε > 0 ) the best differential ratio of 2 / 3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442].

MFCS Conference 2006 Conference Paper

Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

Refael Hassin
Jérôme Monnot
Danny Segev

Abstract Let G = ( V, E ) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function \({\mathcal{L}}: E \rightarrow \mathbb{N}\). In addition, each label ℓ ∈ ℕ to which at least one edge is mapped has a non-negative cost c ( ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I ⊆ ℕ such that the edge set \(\{ e \in E: {\mathcal {L}}( e ) \in I \}\) forms a connected subgraph spanning all vertices. Similarly, in the minimum label s -t path problem (MinLP) the goal is to identify an s - t path minimizing the combined cost of its labels, where s and t are provided as part of the input. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP. As a secondary objective, we make a concentrated effort to relate the algorithmic methods utilized in approximating these problems to a number of well-known techniques, originally studied in the context of integer covering.

TCS Journal 2005 Journal Article

On the differential approximation of MIN SET COVER

Cristina Bazgan
Jérôme Monnot
Vangelis Th. Paschos
Fabrice Serrière

We present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by 1. 365 / Δ and above by 4 / ( Δ + 1 ), where Δ is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i. e. , solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by 2 / ( Δ + 1 ) and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of 1 / Δ. Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms.