Author name cluster

Arnaud Mary

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.

3 papers

2 author rows

MFCS Conference 2019 Conference Paper

The Perfect Matching Reconfiguration Problem

Marthe Bonamy
Nicolas Bousquet 0001
Marc Heinrich
Takehiro Ito
Yusuke Kobayashi 0001
Arnaud Mary
Moritz Mühlenthaler
Kunihiro Wasa

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

Details

TCS Journal 2017 Journal Article

Algorithms for k-meet-semidistributive lattices

Laurent Beaudou
Arnaud Mary
Lhouari Nourine

In this paper we consider k-meet-semidistributive lattices and we are interested in the computation of the set-colored poset associated to an implicational base. The parameter k is of interest since for any finite lattice L there exists an integer k for which L is k-meet-semidistributive. When k = 1 they are known as meet-semidistributive lattices. We first give a polynomial time algorithm to compute an implicational base of a k-meet-semidistributive lattice from its associated colored poset. In other words, for a fixed k, finding a minimal implicational base of a k-meet-semidistributive lattice L from a context (FCA literature) of L can be done not just in output-polynomial time (which is open in the general case) but in polynomial time in the size of the input. This result generalizes that in [26]. Second, we derive an algorithm to compute a set-colored poset from an implicational base which is based on the enumeration of minimal transversals of a hypergraph and turns out to be in polynomial time for k-meet-semidistributive lattices [13, 20]. Finally, we show that checking whether a given implicational base describes a k-meet-semidistributive lattice can be done in polynomial time.

Details DOI

TCS Journal 2015 Journal Article

An average study of hypergraphs and their minimal transversals

Julien David
Loïck Lhote
Arnaud Mary
François Rioult

In this paper, we study some average properties of hypergraphs and the average complexity of algorithms applied to hypergraphs under different probabilistic models. Our approach is both theoretical and experimental since our goal is to obtain a random model that is able to capture the real-data complexity. Starting from a model that generalizes the Erdös–Renyi model [10, 11], we obtain asymptotic estimations on the average number of transversals, irredundants and minimal transversals in a random hypergraph. We use those results to obtain an upper bound on the average complexity of algorithms to generate the minimal transversals of a hypergraph. Then we make our random model more complex in order to bring it closer to real-data and identify cases where the average number of minimal transversals is at most polynomial, quasi-polynomial or exponential.

Details DOI