4 papers · 1 filter
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…