Govind S. Sankar

activity

20212025

most citedDegrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth

5 citations · 10 across the 7 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.CC2021

Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)

Dániel Marx, Govind S. Sankar, Philipp Schepper

In the general AntiFactor problem, a graph $G$ is given with a set $X_{v} \subseteq N$ of forbidden degrees for every vertex $v$ and the task is to find a set $S$ of edges su…

cs.DS2021

Matchings with Group Fairness Constraints: Online and Offline Algorithms

Govind S. Sankar, Anand Louis, Meghana Nasre +1

We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this…

cs.CC2021★ 5 cited

Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth

Dániel Marx, Govind S. Sankar, Philipp Schepper

For the General Factor problem we are given an undirected graph $G$ and for each vertex $v \in V (G)$ a finite set $B_{v}$ of non-negative integers. The task is to decide if there is a…