43 citations · 538 across the 74 of their papers we have counts for
83 papers
Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung +3
We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is -quasi-shortest f…
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer and a simple, undirected, and unweighted graph , the objective…
A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning +1
A set of vertices in a graph is a dominating set of if every vertex not in has a neighbor in , where two vertices are neighbors if they are adjacent. The dominat…
Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1
The neighbourhood complexity of a graph is a quantity measuring, for a graph and an integer , the maximum possible number (over all vertex subsets of size…
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 of vertices of a graph is a \textit{geodetic se…
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 such that every vertex lies on a shortest directed path between two verti…
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 and integer , and the objective is to decide whether there exists a vertex subset of size such that any vertex i…
Locating-dominating coalitions in graphs
M. Chellali, A. A. Dobrynin, F. Foucaud +2
A set of vertices in a graph is a locating-dominating set (LD-set) if it is dominating and every two vertices , of satisfy $N(u) \cap D \neq…
Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
Florent Foucaud, Atrayee Majumder, Tobias Mömke +1
In the PATH COVER problem, one asks to cover the vertices of a graph using the smallest possible number of (not necessarily disjoint) paths. While the variant where the paths need…
The Parameterized Complexity of Computing the VC-Dimension
Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney +1
The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new re…
Parameterized complexity of isometric path partition: treewidth and diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth () of the input graph, arguably one of the most…
Distance-based (and path-based) covering problems for graphs of given cyclomatic number
Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen
We study a large family of graph covering problems, whose definitions rely on distances, for graphs of bounded cyclomatic number (that is, the minimum number of edges that need to…
Locating-dominating partitions for some classes of graphs
Florent Foucaud, Paras Vinubhai Maniya, Kaustav Paul +1
A dominating set of a graph is a set such that every vertex in is adjacent to at least one vertex in . A set is a loc…
Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
Florent Foucaud, Arti Pandey, Kaustav Paul
Given a graph , a set is said to be a monitoring edge-geodetic set if the deletion of any edge in the graph results in a change in the distance between at l…
Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
Dibyayan Chakraborty, Florent Foucaud
The (strong) isometric path complexity is a recently introduced graph invariant that captures how arbitrary isometric paths (i.e., shortest paths) of a graph can be viewed as a uni…
Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
Laurent Beaudou, Jan Bok, Florent Foucaud +2
The \emph{-neighbourhood complexity} of a graph is the function counting, for a given integer , the largest possible number, over all vertex-subsets of size , of s…
Structural Parameterization of Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate structural parameterizations of two identification problems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph on vertices an…
Algorithms and complexity for monitoring edge-geodetic sets in graphs
Florent Foucaud, Clara Marcille, R. B. Sandeep +2
A monitoring edge-geodetic set of a graph is a subset of its vertices such that for every edge in the graph, deleting increases the distance between at least one pair o…
Monitoring arc-geodetic sets of oriented graphs
Tapas Das, Florent Foucaud, Clara Marcille +2
Monitoring edge-geodetic sets in a graph are subsets of vertices such that every edge of the graph must lie on all the shortest paths between two vertices of the monitoring set. Th…
Identifying open codes in trees and 4-cycle-free graphs of given maximum degree
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning
An identifying open code of a graph is a set of vertices that is both a separating open code (that is, for all distinct vertices and $…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud +1
In this paper, we study a dynamic analogue of the Path Cover problem, which can be solved in polynomial-time in directed acyclic graphs. A temporal digraph has an arc set that chan…
Identifying codes in triangle-free graphs of bounded maximum degree
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning +1
An identifying code of a closed-twin-free graph is a set of vertices of such that any two vertices in have a distinct, nonempty intersection between their closed ne…
Identifying codes in graphs of given maximum degree: Characterizing trees
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning +1
An identifying code of a closed-twin-free graph is a dominating set of vertices of such that any two vertices in have a distinct intersection between their closed n…