Source author record

Satyabrata Jana

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

FPT Approximations for Connected Maximum Coverage

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph $G$ and an auxiliary connectivity graph $G_{conn}$ on red vertices, and integers $k, t$ , the task is to find a $k$ -sized subset of red vertices that dominates at least $t$ blue vertices, and that induces a connected subgraph in $G_{conn}$ . This formulation captures connected variants of Max Coverage, Partial Dominating Set, and Partial Vertex Cover studied in prior literature. After identifying (parameterized) inapproximability results inherited from known problems, we first show that the problem is fixed-parameter tractable by $t$ . Furthermore, when the bipartite graph excludes $K_{d,d}$ as a subgraph, we design (resp. efficient) parameterized approximation schemes for approximating $t$ (resp. $k$ ). Notably, these FPT approximations do not impose any restrictions on $G_{conn}$ . Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.

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

Maximum Bipartite Subgraph of Geometric Intersection Graphs

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set $S$ of $n$ geometric objects in the plane, we want to compute a maximum-size subset $S'\subseteq S$ such that the intersection graph of the objects in $S'$ is bipartite. We first give a simple $O(n)$ -time algorithm that solves the MBS problem on a set of $n$ intervals. We also give an $O(n^2)$ -time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. We show that the MBS problem is NP-hard on geometric graphs for which the maximum independent set is NP-hard (hence, it is NP-hard even on unit squares and unit disks). On the other hand, we give a PTAS for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (TFS), where the objective is the same as that of MBS except the intersection graph induced by the set $S'$ needs to be triangle-free only (instead of being bipartite).

preprint2016arXiv

Uniquely Restricted Matchings in Interval Graphs

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$ . We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. ("Uniquely restricted matchings", M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality "strong independent set" in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.

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.