2 citations · 4 across the 20 of their papers we have counts for
7 papers · 1 filter
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…
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…
A Single Exponential-Time FPT Algorithm for Cactus Contraction
R. Krithika, Pranabendu Misra, Prafullkumar Tale
For a collection of graphs, the -\textsc{Contraction} problem takes a graph and an integer as input and decides if can be modified to some gr…
Path Contraction Faster than
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov +2
A graph is contractible to a graph if there is a set , such that is isomorphic to . Here, is the graph obtained from by contracting all…
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
Prafullkumar Tale
In the \textsc{Geodetic Set} problem, the input consists of a graph and a positive integer . The goal is to determine whether there exists a subset of vertices of size $…