Source author record

Jérôme Monnot

Jérôme Monnot appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Artificial Intelligence Computer Science and Game Theory Discrete Mathematics math.CO

Catalog footprint

What is connected

6works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Strong cliques in diamond-free graphs

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 remain intractable 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 two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These 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.

preprint2016arXiv

Subset Sum Problems With Digraph Constraints

We introduce and study four optimization problems that generalize the well-known subset sum problem. Given a node-weighted digraph, select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints need to be satisfied. The (weak resp.) digraph constraint imposes that if (all incoming nodes of resp.) a node $x$ belongs to the solution, then the latter comprises all its outgoing nodes (node $x$ itself resp.). The maximality constraint ensures that a solution cannot be extended without violating the budget or the (weak) digraph constraint. We study the complexity of these problems and we present some approximation results according to the type of digraph given in input, e.g. directed acyclic graphs and oriented trees. Key words. Subset Sum, Maximal problems, digraph constraints, complexity, directed acyclic graphs, oriented trees, PTAS.

preprint2016arXiv

Upper Domination: towards a dichotomy through boundary properties

An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in classes of graphs defined by finitely many forbidden induced subgraphs and conjecture that the problem admits a dichotomy in this family, i.e. it is either NP-hard or polynomial-time solvable for each class in the family. A helpful tool to study the complexity of an algorithmic problem on finitely defined classes of graphs is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem and prove the dichotomy for classes defined by a single forbidden induced subgraph.

preprint2015arXiv

Algorithmic Aspects of Upper Domination

In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a full classification of the related maximisation and minimisation problems, as well as the related parameterised problems, on general graphs and on graphs of bounded degree, and we also study planar graphs.

preprint2011arXiv

New Candidates Welcome! Possible Winners with respect to the Addition of New Candidates

In voting contexts, 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. We give a computational study of this problem, focusing on scoring rules, and we provide a formal comparison with related problems such as control via adding candidates or cloning.

preprint2010arXiv

Minimum regulation of uncoordinated matchings

Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. A possible way to cope with selfishness is to compute a desired outcome (if it is tractable) and impose it. However this answer is often inappropriate because compelling an agent can be costly, unpopular or just hard to implement. Since both situations (no coordination and full coordination) show opposite advantages and drawbacks, it is natural to study possible tradeoffs. In this paper we study a strategic game where the nodes of a simple graph G are independent agents who try to form pairs: e.g. jobs and applicants, tennis players for a match, etc. In many instances of the game, a Nash equilibrium significantly deviates from a social optimum. We analyze a scenario where we fix the strategy of some players; the other players are free to make their choice. The goal is to compel a minimum number of players and guarantee that any possible equilibrium of the modified game is a social optimum, i.e. created pairs must form a maximum matching of G. We mainly show that this intriguing problem is NP-hard and propose an approximation algorithm with a constant ratio.