F. Foucaud

activity

20242026

collaborators

26 papers

cs.DM2026

Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

GaÃ©tan Berthe, Florent Foucaud, Tuomo LehtilÃ¤ +1

The neighbourhood complexity $n c (G, k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$ , the maximum possible number (over all vertex subsets $S$ of size…

cs.DS2026

Algorithms and complexity for geodetic sets on interval and chordal graphs

Dibyayan Chakraborty, Sandip Das, Florent Foucaud +2

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic se…

cs.DS2026

Structural parameterizations of Geodetic Set on directed (acyclic) graphs

Laurent Beaudou, Florent Foucaud, Lucas Lorieau +1

In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set $S \subseteq V (G)$ such that every vertex lies on a shortest directed path between two verti…

cs.DS2026

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Florent Foucaud, Narges Ghareghani, Lucas Lorieau +3

In the GEODETIC SET problem, an input is a (di)graph $G$ and integer $k$ , and the objective is to decide whether there exists a vertex subset $S$ of size $k$ such that any vertex i…

math.CO2026

Locating-dominating partitions for some classes of graphs

Florent Foucaud, Paras Vinubhai Maniya, Kaustav Paul +1

A dominating set of a graph $G$ is a set $D \subseteq V (G)$ such that every vertex in $V (G) ∖ D$ is adjacent to at least one vertex in $D$ . A set $L \subseteq V (G)$ is a loc…

math.CO2026

Locating-dominating coalitions in graphs

M. Chellali, A. A. Dobrynin, F. Foucaud +2

A set $D$ of vertices in a graph $G = (V, E)$ is a locating-dominating set (LD-set) if it is dominating and every two vertices $u$ , $v$ of $V ∖ D$ satisfy $N(u) \cap D \neq…