2 citations · 4 across the 22 of their papers we have counts for
4 papers · 1 filter
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…
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…
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
The Complexity of Contracting Bipartite Graphs into Small Cycles
R. Krithika, Roohani Sharma, Prafullkumar Tale
For a positive integer , the -Contractibility problem takes as input an undirected simple graph and determines whether can be transformed into a graph…