Source author record

Abhishek Sahu

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

ResearcherUnclaimed source record

Discrete Mathematics Artificial Intelligence Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds

The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to infrastructure and legal constraints, kidney exchange can only be performed in small cycles in practice. In reality, there are also some altruistic donors who do not have any paired patients. This allows us to also perform kidney exchange along paths that start from some altruistic donor. Unfortunately, the computational task is NP-complete. To overcome this computational barrier, an important line of research focuses on designing faster algorithms, both exact and using the framework of parameterized complexity. The standard parameter for the kidney exchange problem is the number $t$ of patients that receive a healthy kidney. The current fastest known deterministic FPT algorithm for this problem, parameterized by $t$ , is $O^\star\left(14^t\right)$ . In this work, we improve this by presenting a deterministic FPT algorithm that runs in time $O^\star\left((4e)^t\right)\approx O^\star\left(10.88^t\right)$ . This problem is also known to be W[1]-hard parameterized by the treewidth of the underlying undirected graph. A natural question here is whether the kidney exchange problem admits an FPT algorithm parameterized by the pathwidth of the underlying undirected graph. We answer this negatively in this paper by proving that this problem is W[1]-hard parameterized by the pathwidth of the underlying undirected graph. We also present some parameterized intractability results improving the current understanding of the problem under the framework of parameterized complexity.

preprint2024arXiv

A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion

A proper Helly circular-arc graph is an intersection graph of a set of arcs on a circle such that none of the arcs properly contains any other arc and every set of pairwise intersecting arcs has a common intersection. The Proper Helly Circular-arc Vertex Deletion problem takes as input a graph $G$ and an integer $k$ , and the goal is to check if we can remove at most $k$ vertices from the graph to obtain a proper Helly circular-arc graph; the parameter is $k$ . Recently, Cao et al.~[MFCS 2023] obtained an FPT algorithm for this (and related) problem. In this work, we obtain a polynomial kernel for the problem.

preprint2020arXiv

Parameterized Complexity of Maximum Edge Colorable Subgraph

A graph $H$ is {\em $p$ -edge colorable} if there is a coloring $ψ: E(H) \rightarrow \{1,2,\dots,p\}$ , such that for distinct $uv, vw \in E(H)$ , we have $ψ(uv) \neq ψ(vw)$ . The {\sc Maximum Edge-Colorable Subgraph} problem takes as input a graph $G$ and integers $l$ and $p$ , and the objective is to find a subgraph $H$ of $G$ and a $p$ -edge-coloring of $H$ , such that $|E(H)| \geq l$ . We study the above problem from the viewpoint of Parameterized Complexity. We obtain \FPT\ algorithms when parameterized by: $(1)$ the vertex cover number of $G$ , by using {\sc Integer Linear Programming}, and $(2)$ $l$ , a randomized algorithm via a reduction to \textsc{Rainbow Matching}, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters $p+k$ , where $k$ is one of the following: $(1)$ the solution size, $l$ , $(2)$ the vertex cover number of $G$ , and $(3)$ $l - {\mm}(G)$, where ${\mm}(G)$ is the size of a maximum matching in $G$ ; we show that the (decision version of the) problem admits a kernel with $\mathcal{O}(k \cdot p)$ vertices. Furthermore, we show that there is no kernel of size $\mathcal{O}(k^{1-ε} \cdot f(p))$ , for any $ε> 0$ and computable function $f$ , unless $\NP \subseteq \CONPpoly$.

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.