Source author record

Abhijin Adiga

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Artificial Intelligence math.GN Multiagent Systems physics.soc-ph Social and Information Networks

Catalog footprint

Research overview

12works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks

Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning. We introduce TESTPREV, a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TESTPREV in general. We also show that TESTPREV is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GREEDYMI, that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GREEDYMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model.

preprint2022arXiv

Perturbative methods for mostly monotonic probabilistic satisfiability problems

The probabilistic satisfiability of a logical expression is a fundamental concept known as the partition function in statistical physics and field theory, an evaluation of a related graph's Tutte polynomial in mathematics, and the Moore-Shannon network reliability of that graph in engineering. It is the crucial element for decision-making under uncertainty. Not surprisingly, it is provably hard to compute exactly or even to approximate. Many of these applications are concerned only with a subset of problems for which the solutions are monotonic functions. Here we extend the weak- and strong-coupling methods of statistical physics to heterogeneous satisfiability problems and introduce a novel approach to constructing lower and upper bounds on the approximation error for monotonic problems. These bounds combine information from both perturbative analyses to produce bounds that are tight in the sense that they are saturated by some problem instance that is compatible with all the information contained in either approximation.

preprint2022arXiv

Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise

Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principle's goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

preprint2015arXiv

Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread

The largest eigenvalue of the adjacency matrix of a network (referred to as the spectral radius) is an important metric in its own right. Further, for several models of epidemic spread on networks (e.g., the `flu-like' SIS model), it has been shown that an epidemic dies out quickly if the spectral radius of the graph is below a certain threshold that depends on the model parameters. This motivates a strategy to control epidemic spread by reducing the spectral radius of the underlying network. In this paper, we develop a suite of provable approximation algorithms for reducing the spectral radius by removing the minimum cost set of edges (modeling quarantining) or nodes (modeling vaccinations), with different time and quality tradeoffs. Our main algorithm, \textsc{GreedyWalk}, is based on the idea of hitting closed walks of a given length, and gives an $O(\log^2{n})$ -approximation, where $n$ denotes the number of nodes; it also performs much better in practice compared to all prior heuristics proposed for this problem. We further present a novel sparsification method to improve its running time. In addition, we give a new primal-dual based algorithm with an even better approximation guarantee ( $O(\log n)$ ), albeit with slower running time. We also give lower bounds on the worst-case performance of some of the popular heuristics. Finally we demonstrate the applicability of our algorithms and the properties of our solutions via extensive experiments on multiple synthetic and real networks.

preprint2015arXiv

Sublinear Approximation Algorithms for Boxicity and Related Problems

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$ . Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time $κ(n)$ factor approximation algorithm for computing boxicity and a $κ(n)\lceil \log \log n\rceil$ factor approximation algorithm for computing the cubicity, where $κ(n) =2\left\lceil\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right\rceil$ . These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question paused by Spinrad about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include $O(κ(n))$ factor approximation algorithms for computing the following parameters: the partial order dimension of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, threshold dimension of split graphs and Ferrer's dimension of digraphs. Each of these parameters is inapproximable within an $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems.

preprint2014arXiv

Parameterized and Approximation Algorithms for Boxicity

Boxicity of a graph $G(V,$ $E)$ , denoted by $box(G)$ , is the minimum integer $k$ such that $G$ can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$ . The problem of computing boxicity is inapproximable even for graph classes like bipartite, co-bipartite and split graphs within $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless $NP=ZPP$ . We give FPT approximation algorithms for computing the boxicity of graphs, where the parameter used is the vertex or edge edit distance of the given graph from families of graphs of bounded boxicity. This can be seen as a generalization of the parameterizations discussed in \cite{Adiga2}. Extending the same idea in one of our algorithms, we also get an $O\left(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing boxicity and an $O\left(\frac{n {(\log \log n)}^{\frac{3}{2}}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing the cubicity. These seem to be the first $o(n)$ factor approximation algorithms known for both boxicity and cubicity. As a consequence of this result, a $o(n)$ factor approximation algorithm for computing the partial order dimension of finite posets and a $o(n)$ factor approximation algorithm for computing the threshold dimension of split graphs would follow.

preprint2012arXiv

Cubicity, Degeneracy, and Crossing Number

A $k$ -box $B=(R_1,...,R_k)$ , where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$ . If each $R_i$ is a unit length interval, we call $B$ a $k$ -cube. Boxicity of a graph $G$ , denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$ -boxes. Similarly, the cubicity of $G$ , denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$ -cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $Δ$ , $\cubi(G)\leq \lceil 4(Δ+1)\log n\rceil$. In this paper, we show that, for a $k$ -degenerate graph $G$ , $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $Δ$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$ . An important consequence of the above result is that if the crossing number of a graph $G$ is $t$ , then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$ . We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$ . Using our bound for the cubicity of $k$ -degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$ , where $d_{av}$ denotes the average degree of the graph under consideration.

preprint2012arXiv

Lower Bounds for Boxicity

An axis-parallel $b$ -dimensional box is a Cartesian product $R_1\times R_2\times...\times R_b$ where $R_i$ is a closed interval of the form $[a_i,b_i]$ on the real line. For a graph $G$ , its \emph{boxicity} box(G) is the minimum dimension $b$ , such that $G$ is representable as the intersection graph of boxes in $b$ -dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: (1) The boxicity of a graph on $n$ vertices with no universal vertices and minimum degree $δ$ is at least $n/2(n-δ-1)$ . (2) Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $p \le 1- \frac{40 \log n}{n^2}$ . Then, for $G \in \mathcal{G}(n,p)$ , almost surely $box(G)=Ω(np(1-p))$ . On setting $p=1/2$ we immediately infer that almost all graphs have boxicity $Ω(n)$ . (3) Spectral lower bounds for the boxicity of $k$ -regular graphs. (4) The boxicity of random $k$ -regular graphs on $n$ vertices (where $k$ is fixed) is $Ω(k/\log k)$ . (5) There exists a positive constant $c$ such that almost all balanced bipartite graphs on $2n$ vertices with exactly $m$ edges have boxicity at least $c m/n$ , for $m\le c' n^2/3$ for any positive constant $c' < 1$ .

preprint2011arXiv

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

Boxicity of a graph $G(V,E)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$ -dimensional axis parallel rectangles in $\mathbf{R}^k$ . Equivalently, it is the minimum number of interval graphs on the vertex set $V$ such that the intersection of their edge sets is $E$ . It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below $O(n^{0.5 - ε})$ -factor, for any $ε>0$ in polynomial time unless $NP=ZPP$ . Till date, there is no well known graph class of unbounded boxicity for which even an $n^ε$ -factor approximation algorithm for computing boxicity is known, for any $ε<1$ . In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a $(2+\frac{1}{k})$ -factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where $k \ge 1$ is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is $O(mn+n^2)$ in both these cases and in $O(mn+kn^2)= O(n^3)$ time we also get their corresponding box representations, where $n$ is the number of vertices of the graph and $m$ is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

preprint2011arXiv

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

preprint2010arXiv

Boxicity and Poset Dimension

Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and edge set $E(G)$ . A $k$ -dimensional box is a Cartesian product of closed intervals $[a_1,b_1]\times [a_2,b_2]\times...\times [a_k,b_k]$ . The {\it boxicity} of $G$ , $\boxi(G)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$ -dimensional boxes, i.e. each vertex is mapped to a $k$ -dimensional box and two vertices are adjacent in $G$ if and only if their corresponding boxes intersect. Let $\poset=(S,P)$ be a poset where $S$ is the ground set and $P$ is a reflexive, anti-symmetric and transitive binary relation on $S$ . The dimension of $\poset$, $\dim(\poset)$ is the minimum integer $t$ such that $P$ can be expressed as the intersection of $t$ total orders. Let $G_\poset$ be the \emph{underlying comparability graph} of $\poset$, i.e. $S$ is the vertex set and two vertices are adjacent if and only if they are comparable in $\poset$. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset $\poset$, $\boxi(G_\poset)/(χ(G_\poset)-1) \le \dim(\poset)\le 2\boxi(G_\poset)$, where $χ(G_\poset)$ is the chromatic number of $G_\poset$ and $χ(G_\poset)\ne1$. It immediately follows that if $\poset$ is a height-2 poset, then $\boxi(G_\poset)\le \dim(\poset)\le 2\boxi(G_\poset)$ since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph $G$ with a natural partial order associated with the \emph{extended double cover} of $G$ , denoted as $G_c$ : Note that $G_c$ is a bipartite graph with partite sets $A$ and $B$ which are copies of $V(G)$ such that corresponding to every $u\in V(G)$ , there are two vertices $u_A\in A$ and $u_B\in B$ and $\{u_A,v_B\}$ is an edge in $G_c$ if and only if either $u=v$ or $u$ is adjacent to $v$ in $G$ . Let $\poset_c$ be the natural height-2 poset associated with $G_c$ by making $A$ the set of minimal elements and $B$ the set of maximal elements. We show that $\frac{\boxi(G)}{2} \le \dim(\poset_c) \le 2\boxi(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\poset)\le 2\boxi(G_\poset)$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\poset)\le 2\tw(G_\poset)+4$, since boxicity of any graph is known to be at most its $\tw+2$. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree $Δ$ is $O(Δ\log^2Δ)$ which is an improvement over the best known upper bound of $Δ^2+2$ . (2) There exist graphs with boxicity $Ω(Δ\logΔ)$ . This disproves a conjecture that the boxicity of a graph is $O(Δ)$ . (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on $n$ vertices with a factor of $O(n^{0.5-ε})$ for any $ε>0$ , unless $NP=ZPP$ .

preprint2010arXiv

The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

A $k$ -dimensional box is the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$ , denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$ -dimensional boxes. A unit cube in $k$ -dimensional space or a $k$ -cube is defined as the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$ . The {\it cubicity} of $G$ , denoted as $\cub(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$ -cubes. The {\it threshold dimension} of a graph $G(V,E)$ is the smallest integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of $G$ . In this paper we will show that there exists no polynomial-time algorithm to approximate the threshold dimension of a graph on $n$ vertices with a factor of $O(n^{0.5-ε})$ for any $ε>0$ , unless $NP=ZPP$ . From this result we will show that there exists no polynomial-time algorithm to approximate the boxicity and the cubicity of a graph on $n$ vertices with factor $O(n^{0.5-ε})$ for any $ε>0$ , unless $NP=ZPP$ . In fact all these hardness results hold even for a highly structured class of graphs namely the split graphs. We will also show that it is NP-complete to determine if a given split graph has boxicity at most 3.

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.

Abhijin Adiga

Research overview

Is this your work?

12 publications

Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks

Perturbative methods for mostly monotonic probabilistic satisfiability problems

Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise

Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread

Sublinear Approximation Algorithms for Boxicity and Related Problems

Parameterized and Approximation Algorithms for Boxicity

Cubicity, Degeneracy, and Crossing Number

Lower Bounds for Boxicity

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

Boxicity and Poset Dimension

The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

See the researcher in context

Building this map preview