Sukanya Pandey

activity

20242026

collaborators

5 papers

cs.DS2026

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs

Thekla Hamm, Sukanya Pandey, Krisztina SzilÃ¡gyi

Given a planar graph, a subset of its vertices called terminals, and $k \in N$ , the Face Cover Number problem asks whether the terminals lie on the boundaries of at most $…

cs.DS2025

Planar Multiway Cut with Terminals on Few Faces

Sukanya Pandey, Erik Jan van Leeuwen

We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in $n^{O (t)}$ time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{…

math.CO2025

Computing Subset Vertex Covers in $H$ -Free Graphs

Nick Brettell, Jelle J. Oostveen, Sukanya Pandey +3

We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph $G = (V, E)$ , a subset $T \subseteq V$ and integer $k$ , if $V$ has…

cs.CC2024

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs

Matthew Johnson, Barnaby Martin, Siani Smith +3

We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves…

cs.DM2024

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs

Vadim Lozin, Barnaby Martin, Sukanya Pandey +4

For a fixed set $H$ of graphs, a graph $G$ is $H$ -subgraph-free if $G$ does not contain any $H \in H$ as a (not necessarily induced) subgraph. A recently propo…