17 papers
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…
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 Biclique Contraction and Balanced Biclique Contraction
R. Krithika, V. K. Kutty Malu, Roohani Sharma +1
In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objectiv…
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…