5 papers
Multidimensional Budget-Feasible Mechanism Design
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested players. We have a valuation function ,…
An -approximate budget feasible mechanism for subadditive valuations
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, there is a set of items , each owned by a distinct seller. The seller of item incurs a private cost for supplying her i…
Recognizing -Clique Extendible Orderings
Mathew Francis, Rian Neogi, Venkatesh Raman
A graph is -clique-extendible if there is an ordering of the vertices such that whenever two -sized overlapping cliques and have common vertices, and these comm…
On the Parameterized Complexity of Deletion to -free Strong Components
Rian Neogi, M. S. Ramanujan, Saket Saurabh +1
{\sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the s…
Tractability of Konig Edge Deletion Problems
Diptapriyo Majumdar, Rian Neogi, Venkatesh Raman +1
A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph t…