Source author record

Stephane Bessy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Arc-disjoint in- and out-branchings in digraphs of independence number at most 2

We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching $B^+$ and an in-branching $B^-$ which are arc-disjoint (we call such branchings good pair). This is best possible in terms of the arc-connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in-and out-degrees that have good no pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and give an example of a 2-arc-strong digraph $D$ on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc-connectivity 2 that have no good pair. Finally we pose a number of open problems.

preprint2016arXiv

Antistrong digraphs

An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices $x,y$ in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph $D$ is antistrong if it contains an antidirected $(x,y)$ -trail starting and ending with a forward arc for every choice of $x,y\in V(D)$ . We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to $D$ makes the resulting digraph the arc-disjoint union of $k$ antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.

preprint2015arXiv

Bounds on the Exponential Domination Number

As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if $S$ is a set of vertices of a graph $G$ , then $S$ is an exponential dominating set of $G$ if $\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}\geq 1$ for every vertex $u$ in $V(G)\setminus S$ , where ${\rm dist}_{(G,S)}(u,v)$ is the distance between $u\in V(G)\setminus S$ and $v\in S$ in the graph $G-(S\setminus \{ v\})$ . The exponential domination number $γ_e(G)$ of $G$ is the minimum order of an exponential dominating set of $G$ . Dankelmann et al. show $\frac{1}{4}({\rm d}+2)\leq γ_e(G)\leq \frac{2}{5}(n+2)$ for a connected graph $G$ of order $n$ and diameter ${\rm d}$ . We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph $G$ of order $n$ , maximum degree $Δ$ at least $3$ , radius ${\rm r}$ at least $1$ , we show \begin{eqnarray*} γ_e(G) & \geq & \left(\frac{n}{13(Δ-1)^2}\right)^{\frac{\log_2(Δ-1)+1}{\log_2^2(Δ-1)+\log_2(Δ-1)+1}},\\[3mm] γ_e(G) & \leq & 2^{2{\rm r}-2}\mbox{, and }\\[3mm] γ_e(G) & \leq & \frac{43}{108}(n+2). \end{eqnarray*}

preprint2015arXiv

On independent set on B1-EPG graphs

In this paper we consider the Maximum Independent Set problem (MIS) on $B_1$ -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersinglebend} as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$ -EPG denotes EPG-graphs where every path has at most $k$ bends. The study of MIS on $B_1$ -EPG graphs has been initiated in~\cite{wadsMIS} where authors prove that MIS is NP-complete on $B_1$ -EPG graphs, and provide a polynomial $4$ -approximation. In this article we study the approximability and the fixed parameter tractability of MIS on $B_1$ -EPG. We show that there is no PTAS for MIS on $B_1$ -EPG unless P $=$ NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most $3$ . This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on $B_1$ -EPG restricted to only three shapes of path, and $W_1$ -hard on $B_2$ -EPG. The status for general $B_1$ -EPG (with the four shapes) is left open.

preprint2008arXiv

Polynomial kernels for 3-leaf power graph modification problems

A graph G=(V,E) is a 3-leaf power iff there exists a tree T whose leaves are V and such that (u,v) is an edge iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion, are FTP when parameterized by the size of the edge set modification. However polynomial kernel was known for none of these three problems. For each of them, we provide cubic kernels that can be computed in linear time for each of these problems. We thereby answer an open problem first mentioned by Dom, Guo, Huffner and Niedermeier (2005).

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.