BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Venkatesh Raman

Venkatesh Raman contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete Mathematicsmath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

9 published item(s)

preprint2021arXiv

Approximation in (Poly-) Logarithmic Space

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d-Hitting Set that runs in time n^{O(d^2 + d/ε})}, uses O((d^2 + d/ε) log n) bits of space, and achieves an approximation ratio of O((d/ε) n^ε) for any positive ε\leq 1 and any natural number d. In particular, this yields a factor-O(log n) approximation algorithm which runs in time n^{O(log n)} and uses O(log^2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for Vertex Cover and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for Vertex Cover on graphs with maximum degree Δ, and an algorithm for computing maximal independent sets which both run in time n^{O(Δ)} and use O(Δlog n) bits of space. For the more general d-Hitting Set problem, we devise a factor-d approximation algorithm which runs in time n^{O(d δ^2)} and uses O(d δ^2 log n) bits of space on set families where each element appears in at most δsets. For Independent Set restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O(log n) bits of space. We also devise a factor-O(d^2) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and uses O(log^2 n) bits of space. For d-regular graphs, we show how a known randomized factor-O(log d) approximation algorithm can be derandomized to run in time n^{O(1)} and use O(log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Space-Efficient FPT Algorithms

We prove algorithmic results showing that a number of natural parameterized problems are in the restricted-space parameterized classes Para-L and FPT+XL. The first class comprises problems solvable in f(k) n^{O(1)} time using g(k) + O(log n)) bits of space (k is the parameter and n is the input size; f and g are computable functions). The second class comprises problems solvable under the same time bound, but using g(k) log n bits of space instead. Earlier work on these classes has focused largely on their structural aspects and their relationships with various other classes. We complement this with Para-L and FPT+XL algorithms for a restriction of Hitting Set, some graph deletion problems where the target class has an infinite forbidden set characterization, a number of problems parameterized by vertex cover number, and Feedback Vertex Set.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fixed-parameter tractable algorithms for Tracking Shortest Paths

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System help to show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Kernels for Tracking Path Problem

Tracking of moving objects is crucial to security systems and networks. Given a graph $G$, terminal vertices $s$ and $t$, and an integer $k$, the \textsc{Tracking Paths} problem asks whether there exists at most $k$ vertices, which if marked as trackers, would ensure that the sequence of trackers encountered in each s-t path is unique. It is known that the problem is NP-hard and admits a kernel (reducible to an equivalent instance) with $\mathcal{O}(k^6)$ vertices and $\mathcal{O}(k^7)$ edges, when parameterized by the size of the output (tracking set) $k$ [5]. An interesting question that remains open is whether the existing kernel can be improved. In this paper we answer this affirmatively: (i) For general graphs, we show the existence of a kernel of size $\mathcal{O}(k^2)$, (ii) For planar graphs, we improve this further by giving a kernel of size $\mathcal{O}(k)$. In addition, we also show that finding a tracking set of size at most $n-k$ for a graph on $n$ vertices is hard for the parameterized complexity class W[1], when parameterized by $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recognizing $k$-Clique Extendible Orderings

A graph is $k$-clique-extendible if there is an ordering of the vertices such that whenever two $k$-sized overlapping cliques $A$ and $B$ have $k-1$ common vertices, and these common vertices appear between the two vertices $a,b\in (A\setminus B)\cup (B\setminus A)$ in the ordering, there is an edge between $a$ and $b$, implying that $A\cup B$ is a $(k+1)$-sized clique. Such an ordering is said to be a $k$-C-E ordering. These graphs arise in applications related to modelling preference relations. Recently, it has been shown that a maximum sized clique in such a graph can be found in $n^{O(k)}$ time when the ordering is given. When $k$ is $2$, such graphs are precisely the well-known class of comparability graphs and when $k$ is $3$ they are called triangle-extendible graphs. It has been shown that triangle-extendible graphs appear as induced subgraphs of visibility graphs of simple polygons, and the complexity of recognizing them has been mentioned as an open problem in the literature. While comparability graphs (i.e. $2$-C-E graphs) can be recognized in polynomial time, we show that recognizing $k$-C-E graphs is NP-hard for any fixed $k \geq 3$ and co-NP-hard when $k$ is part of the input. While our NP-hardness reduction for $k \geq 4$ is from the betweenness problem, for $k=3$, our reduction is an intricate one from the $3$-colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a $k$-C-E ordering, and that of finding an $\ell$-sized (or maximum sized) clique in a $k$-C-E graph, given a $k$-C-E ordering, are complete for the parameterized complexity classes co-W[1] and W[1] respectively, when parameterized by $k$. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Structural Parameterizations of Tracking Paths Problem

Given a graph $G$ with source and destination vertices $s,t\in V(G)$ respectively, \textsc{Tracking Paths} asks for a minimum set of vertices $T\subseteq V(G)$, such that the sequence of vertices encountered in each simple path from $s$ to $t$ is unique. The problem was proven \textsc{NP}-hard \cite{tr-j} and was found to admit a quadratic kernel when parameterized by the size of the desired solution \cite{quadratic}. Following recent trends, for the first time, we study \textsc{Tracking Paths} with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that \textsc{Tracking Paths} admits fixed-parameter tractable (\textsc{FPT}) algorithms when parameterized by the size of vertex cover, and the size of cluster vertex deletion set for the input graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Structural Parameterizations with Modulator Oblivion

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called `structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a $k$-sized or an approximate ($f(k)$ sized, for a function $f$) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least $k^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ running time when we use the known parameterized or approximation algorithms for finding a $k$-sized chordal deletion set on an $n$ vertex graph. In this work, we design $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ where each bag is a union of four cliques and $\mathcal{O}(k)$ vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are adaptive (robust) in the sense that given an integer $k$, they detect whether the graph has a chordal vertex deletion set of size at most $k$ or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Quartic Kernel for Pathwidth-One Vertex Deletion

The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k); |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G' has O(k^{4}) vertices, and (iii) k' \leq k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O(7^{k} k \cdot n^{2}) time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, {\sc $k$-Leaf Out-Branching}, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{O(\sqrt{k} \log k)} n+ n^{O(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{O(\sqrt{k})}n + n^{O(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely {\sc $k$-Internal Out-Branching}, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{O(\sqrt{k} \log k)} + n^{O(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $ε>0$, the {\sc $k$-Directed Path} problem is solvable in time $O((1+ε)^k n^{f(ε)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

0 citations0 reviewsNo code linkedOpen access