11 citations · 35 across the 50 of their papers we have counts for
4 papers · 1 filter
On -Simple -Path and Related Problems Parameterized by
Gregory Gutin, Magnus Wahlström, Meirav Zehavi
Abasi et al. (2014) and Gabizon et al. (2015) studied the following problems. In the -Simple -Path problem, given a digraph on vertices and integers , decide whe…
Popular Matching in Roommates Setting is NP-hard
Sushmita Gupta, Pranabendu Misra, Saket Saurabh +1
An input to the Popular Matching problem, in the roommates setting, consists of a graph and each vertex ranks its neighbors in strict order, known as its preference. In the Pop…
The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments
R. Krithika, Abhishek Sahu, Saket Saurabh +1
Given a directed graph on vertices and a positive integer , the Arc-Disjoint Cycle Packing problem is to determine whether has arc-disjoint cycles. This problem…
Reducing CMSO Model Checking to Highly Connected Graphs
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh +1
Given a Counting Monadic Second Order (CMSO) sentence , the CMSO problem is defined as follows. The input to CMSO is a graph , and the objective is to determine whe…