Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2025
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…
cs.DS2024
Revisiting Path Contraction and Cycle Contraction
R. Krithika, V. K. Kutty Malu, Prafullkumar Tale
The Path Contraction and Cycle Contraction problems take as input an undirected graph with vertices, edges and an integer and determine whether one can obtain a pat…