Source author record

Pranabendu Misra

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Improving EFX Guarantees through Rainbow Cycle Number

We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$ -EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$ , there always exists a $(1-\varepsilon)$ -EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$ . For all $d \in \mathbb{N}$ , $R(d)$ is the largest $k$ such that there exists a $k$ -partite digraph $G =(\cup_{i \in [k]} V_i, E)$ , in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$ , 2) for any two parts $V_i$ and $V_j$ , each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$ , yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation.

preprint2020arXiv

On Fault Tolerant Feedback Vertex Set

The study of fault-tolerant data structures for various network design problems is a prominent area of research in computer science. Likewise, the study of NP-Complete problems lies at the heart of computer science with numerous results in algorithms and complexity. In this paper we raise the question of computing fault tolerant solutions to NP-Complete problems; that is computing a solution that can survive the "failure" of a few constituent elements. This notion has appeared in a variety of theoretical and practical settings such as estimating network reliability, kernelization (aka instance compression), approximation algorithms and so on. In this paper, we seek to highlight these questions for further research. As a concrete example, we study the fault-tolerant version of the classical Feedback Vertex Set (FVS) problem, that we call Fault Tolerant Feedback Vertex Set (FT-FVS). Recall that, in FVS the input is a graph $G$ and the objective is to compute a minimum subset of vertices $S$ such that $G-S$ is a forest. In FT-FVS, the objective is to compute a minimum subset $S$ of vertices such that $G - (S \setminus \{v\})$ is a forest for any $v \in V(G)$ . Here the vertex $v$ denotes a single vertex fault. We show that this problem is NP-Complete, and then present a constant factor approximation algorithm as well as an FPT-algorithm parameterized by the solution size. We believe that the question of computing fault tolerant solutions to various NP-Complete problems is an interesting direction for future research.

preprint2014arXiv

Deterministic Truncation of Linear Matroids

Let $M=(E,{\cal I})$ be a matroid. A {\em $k$ -truncation} of $M$ is a matroid { $M'=(E,{\cal I}')$ } such that for any $A\subseteq E$ , $A\in {\cal I}'$ if and only if $|A|\leq k$ and $A\in {\cal I}$ . Given a linear representation of $M$ we consider the problem of finding a linear representation of the $k$ -truncation of this matroid. This problem can be abstracted out to the following problem on matrices. Let $M$ be a $n\times m$ matrix over a field $\mathbb{F}$ . A {\em rank $k$ -truncation} of the matrix $M$ is a $k\times m$ matrix $M_k$ (over $\mathbb{F}$ or a related field) such that for every subset $I\subseteq \{1,\ldots,m\}$ of size at most $k$ , the set of columns corresponding to $I$ in $M$ has rank $|I|$ if and only of the corresponding set of columns in $M_k$ has rank $|I|$ . Finding rank $k$ -truncation of matrices is a common way to obtain a linear representation of $k$ -truncation of linear matroids, which has many algorithmic applications. A common way to compute a rank $k$ -truncation of a $n \times m$ matrix is to multiply the matrix with a random $k\times n$ matrix (with the entries from a field of an appropriate size), yielding a simple randomized algorithm. So a natural question is whether it possible to obtain a rank $k$ -truncations of a matrix, {\em deterministically}. In this paper we settle this question for matrices over any finite field or the field of rationals ( $\mathbb Q$ ). We show that given a matrix $M$ over a field $\mathbb{F}$ we can compute a $k$ -truncation $M_k$ over the ring $\mathbb{F}[X]$ in deterministic polynomial time.

preprint2014arXiv

Finding Even Subgraphs Even Faster

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$ , find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$ . They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$ . In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$ . The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.