2 citations · 4 across the 22 of their papers we have counts for
36 papers
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…
On the Hardness of Strong Metric Dimension
Prafullkumar Tale
Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometri…
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…
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…
A Finer View of the Parameterized Landscape of Labeled Graph Contractions
Yashaswini Mathur, Prafullkumar Tale
We study the \textsc{Labeled Contractibility} problem, where the input consists of two vertex-labeled graphs and , and the goal is to determine whether can be obtained f…