3 papers
cs.DM2024
The Parameterized Complexity of Terminal Monitoring Set
N. R. Aravind, Roopam Saxena
In Terminal Monitoring Set (TMS), the input is an undirected graph , together with a collection of terminal pairs and the goal is to find a subset of minimum size…
cs.DS2024
Parameterized Complexity of Path Set Packing
N. R. Aravind, Roopam Saxena
In Path Set Packing, the input is an undirected graph , a collection $\calp$ of simple paths in , and a positive integer . The problem is to decide whether there exist …
cs.DS2024
An FPT algorithm for Matching Cut and d-cut
N R Aravind, Roopam Saxena
Given a positive integer , the d-CUT is the problem of deciding if an undirected graph has a cut such that every vertex in (resp. ) has at most neig…