Author name cluster

Christophe Picouleau

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.

5 papers

1 author row

TCS Journal 2024 Journal Article

On the complexity of Dominating Set for graphs with fixed diameter

Valentin Bouquet
François Delbot
Christophe Picouleau
Stéphane Rovedakis

A set S ⊆ V of a graph G = ( V, E ) is a dominating set if each vertex has a neighbor in S or belongs to S. Dominating Set is the problem of deciding, given a graph G and an integer k ≥ 1, if G has a dominating set of size at most k. It is well known that this problem is NP -complete even for claw-free graphs. We give a (almost) complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter d. We show that the problem is NP -complete for every fixed d ≥ 3 and polynomial-time solvable for d ≤ 2. To prove the case d = 2, we show that Minimum Maximal Matching can be solved in polynomial-time for 2 K 2 -free graphs.

Details DOI

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.

Details DOI

TCS Journal 2021 Journal Article

New sufficient conditions on the degree sequences of uniform hypergraphs

Andrea Frosini
Christophe Picouleau
Simone Rinaldi

The study of the degree sequences of k-uniform hypergraphs, usually called k-sequences, has been a longstanding open problem for the case of k > 2, and the corresponding decision version was proved to be NP-complete recently in 2018 [15]. The problem can be formalized as follows: Given a non decreasing sequence of positive integers π = ( d 1, d 2, …, d n ), can π be the degree sequence of a k-uniform simple hypergraph? If the answer is positive, then the sequence π is said to be k-graphic. For k = 2, that is for simple graphs, Erdös and Gallai [16] provided a characterization of the sequences that are 2-graphic (or simply, graphic). From this characterization, a polynomial time algorithm can be designed to reconstruct the incidence matrix of a graph having a given π as degree sequence (provided this graph exists). Due to the result of [15] and assuming P ≠ N P, an efficiently computable characterization like the one for k = 2 does not even exist for the case of 3-uniform hypergraphs. Necessary or sufficient conditions for π to be k-graphic ( k ≥ 3 ) can be found in the literature. In this paper we prove some different new conditions: first we provide sufficient and also necessary conditions for the case of k-uniform and (almost) regular hypergraphs. Then, for k = 3, we prove sufficient conditions in the case where π can be decomposed into π ′ and π ″, and π ′ is graphic. Most of the results are obtained by borrowing tools from discrete tomography, a current research field on discrete mathematics.

Details DOI

TCS Journal 2018 Journal Article

Contraction and deletion blockers for perfect graphs and H-free graphs

Öznur Yaşar Diner
Daniël Paulusma
Christophe Picouleau
Bernard Ries

We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S = { ec } and S = { vd } and π ∈ { χ, ω, α } for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S = { ec } and S = { vd } and π ∈ { χ, ω, α } restricted to H-free graphs.

Details DOI

TCS Journal 2012 Journal Article

On the NP-completeness of the perfect matching free subgraph problem

Mathieu Lacroix
A. Ridha Mahjoub
Sébastien Martin
Christophe Picouleau

Given a bipartite graph G = ( U ∪ V, E ) such that ∣ U ∣ = ∣ V ∣ and every edge is labelled true or false or both, the perfect matching free subgraph problem is to determine whether or not there exists a subgraph of G containing, for each node u of U, either all the edges labelled true or all the edges labelled false incident to u, and which does not contain a perfect matching. This problem arises in the structural analysis of differential-algebraic systems. The purpose of this paper is to show that this problem is NP-complete. We show that the problem is equivalent to the stable set problem in a restricted case of tripartite graphs. Then we show that the latter remains NP-complete in that case. We also prove the NP-completeness of the related minimum blocker problem in bipartite graphs with perfect matching.

Details DOI