6 papers
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Shubhada Aute, Fahad Panolan, Geevarghese Philip
An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper i…
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
Shubhada Aute, Fahad Panolan, Geevarghese Philip
Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its gene…
Exact Algorithms for Edge Deletion to Cactus
Sheikh Shakil Akhtar, Geevarghese Philip
We study two related problems on simple, un-directed graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general gr…
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
Geevarghese Philip, Erlend Raa Vågset
The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has be…
Space Efficient Algorithms for Parameterised Problems
Sheikh Shakil Akhtar, Pranabendu Misra, Geevarghese Philip
We study "space efficient" FPT algorithms for graph problems with limited memory. Let n be the size of the input graph and k be the parameter. We present algorithms that run in tim…
Faster Algorithms for Graph Monopolarity
Geevarghese Philip, Shrinidhi Teganahally Sridhara
A graph is if its vertex set admits a partition where is a and is an $\textit{independent…