N. R. Aravind
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
N. R. Aravind has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
R. B. Sandeep
Department of Computer Science & Engineering Indian Institute of Technology Hyderabad India
4 shared publications- Naveen Sivadasan
TCS Innovation Labs Hyderabad India
3 shared publications Subrahmanyam Kalyanasundaram
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING IIT HYDERABAD HYDERABAD INDIA
3 shared publicationsAnjeneya Swami Kare
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING IIT HYDERABAD HYDERABAD INDIA
2 shared publications- Naveen Sivadasan
Department of Computer Science & Engineering Indian Institute of Technology Hyderabad India
2 shared publications - Pushkar S. Joglekar
Vishwakarma Institute of Technology, Pune, India
2 shared publications
Latest Publications
- Open Access
Towards a conjecture on long induced rainbow paths in triangle-free graphs
Given a triangle-free graph $G$ with chromatic number $k$ and a proper vertex coloring $φ$ of $G$, it is conjectured that $G$ contains an induced rainbow path on $k$ vertices under $φ$. Scott and Seymour proved the existence of an induced rainbow path on $(\log \log \log k)^{\frac{1}{3}- o(1)}$ vertices. We improve this to $(\log k)^{\frac{1}{2}- o(1)}$ vertices. Further, we prove the existence of an induced path that sees $\frac{k}{2}$ colors.Open AccessTowards a conjecture on long induced rainbow paths in triangle-free graphs
Given a triangle-free graph $G$ with chromatic number $k$ and a proper vertex coloring $φ$ of $G$, it is conjectured that $G$ contains an induced rainbow path on $k$ vertices under $φ$. Scott and Seymour proved the existence of an induced rainbow path on $(\log \log \log k)^{\frac{1}{3}- o(1)}$ vertices. We improve this to $(\log k)^{\frac{1}{2}- o(1)}$ vertices. Further, we prove the existence of an induced path that sees $\frac{k}{2}$ colors. - 1 October 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 319, 254-270
Vertex partitioning problems on graphs with bounded tree width
- 1 October 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 319, 254-270
Vertex partitioning problems on graphs with bounded tree width
- 26 August 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 319, 216-222
Planar projections of graphs
- 26 August 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 319, 216-222
Planar projections of graphs
- Open Access
An FPT algorithm for Matching Cut and d-cut
Given a positive integer $d$, the $d$-CUT problem is to decide if an undirected graph $G=(V,E)$ has a non trivial bipartition $(A,B)$ of $V$ such that every vertex in $A$ (resp. $B$) has at most $d$ neighbors in $B$ (resp. $A$). When $d=1$, this is the MATCHING CUT problem. Gomes and Sau, in IPEC 2019, gave the first fixed parameter tractable algorithm for $d$-CUT, when parameterized by maximum number of the crossing edges in the cut (i.e. the size of edge cut). However, their paper doesn't provide an explicit bound on the running time, as it indirectly relies on a MSOL formulation and Courcelle's Theorem. Motivated by this, we design and present an FPT algorithm for the MATCHING CUT (and more generally for $d$-CUT) for general graphs with running time $2^{O(k\log k)}n^{O(1)}$ where $k$ is the maximum size of the edge cut. This is the first FPT algorithm for the MATCHING CUT (and $d$-CUT) with an explicit dependence on this parameter. We also observe a lower bound of $2^{\Omega(k)}n^{O(1)}$ with same parameter for MATCHING CUT assuming ETH.Open AccessAn FPT algorithm for Matching Cut and d-cut
Given a positive integer $d$, the $d$-CUT problem is to decide if an undirected graph $G=(V,E)$ has a non trivial bipartition $(A,B)$ of $V$ such that every vertex in $A$ (resp. $B$) has at most $d$ neighbors in $B$ (resp. $A$). When $d=1$, this is the MATCHING CUT problem. Gomes and Sau, in IPEC 2019, gave the first fixed parameter tractable algorithm for $d$-CUT, when parameterized by maximum number of the crossing edges in the cut (i.e. the size of edge cut). However, their paper doesn't provide an explicit bound on the running time, as it indirectly relies on a MSOL formulation and Courcelle's Theorem. Motivated by this, we design and present an FPT algorithm for the MATCHING CUT (and more generally for $d$-CUT) for general graphs with running time $2^{O(k\log k)}n^{O(1)}$ where $k$ is the maximum size of the edge cut. This is the first FPT algorithm for the MATCHING CUT (and $d$-CUT) with an explicit dependence on this parameter. We also observe a lower bound of $2^{\Omega(k)}n^{O(1)}$ with same parameter for MATCHING CUT assuming ETH. - Open Access
Structure and colour in triangle-free graphs
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$. Even if one only demands an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'.Open AccessStructure and colour in triangle-free graphs
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$. Even if one only demands an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'. - 24 January 2020
- Published by Springer Nature
- p. 453-462
Planar Projections of Graphs
- Open Access
Bipartitioning Problems on Graphs with Bounded Tree-Width
For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two non-empty sets A and B such that neither the induced graph G[A] nor G[B] contain H (i) as a subgraph? (ii) as an induced subgraph? These problems are NP-complete and are expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle's theorem implies linear time solvability on graphs with bounded tree-width. This approach yields algorithms with running time f(|phi|, t) * n, where |phi| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f(|phi|, t) on |phi| can be as bad as a tower of exponentials. In this paper, we present explicit combinatorial algorithms for these problems for graphs G whose tree-width is bounded. We obtain 2^{O(t^r)} * n time algorithms when H is any fixed graph of order r. In the special case when H = K_r, a complete graph on r vertices, we get an 2^{O(t+r \log t)} * n time algorithm. The techniques can be extended to provide FPT algorithms to determine the smallest number q such that V can be partitioned into q parts such that none of the parts have H as a subgraph (induced subgraph).
Open AccessBipartitioning Problems on Graphs with Bounded Tree-Width
For an undirected graph G, we consider the following problems: given a fixed graph H, can we partition the vertices of G into two non-empty sets A and B such that neither the induced graph G[A] nor G[B] contain H (i) as a subgraph? (ii) as an induced subgraph? These problems are NP-complete and are expressible in monadic second order logic (MSOL). The MSOL formulation, together with Courcelle's theorem implies linear time solvability on graphs with bounded tree-width. This approach yields algorithms with running time f(|phi|, t) * n, where |phi| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f(|phi|, t) on |phi| can be as bad as a tower of exponentials. In this paper, we present explicit combinatorial algorithms for these problems for graphs G whose tree-width is bounded. We obtain 2^{O(t^r)} * n time algorithms when H is any fixed graph of order r. In the special case when H = K_r, a complete graph on r vertices, we get an 2^{O(t+r \log t)} * n time algorithm. The techniques can be extended to provide FPT algorithms to determine the smallest number q such that V can be partitioned into q parts such that none of the parts have H as a subgraph (induced subgraph).
- Open Access
Algorithms and hardness results for happy coloring problems
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of happy edges. When we want to maximize the number of happy vertices, the problem is known as Maximum Happy Vertices (k-MHV). We further study the complexity of the problems and their weighted variants. For instance, we prove that for every k >= 3, both problems are NP-complete for bipartite graphs and k-MHV remains hard for split graphs. In terms of exact algorithms, we show both problems can be solved in time O*(2^n), and give an even faster O*(1.89^n)-time algorithm when k = 3. From a parameterized perspective, we give a linear vertex kernel for Weighted k-MHE, where edges are weighted and the goal is to obtain happy edges of at least a specified total weight. Finally, we prove both problems are solvable in polynomial-time when the graph has bounded treewidth or bounded neighborhood diversity.
Open AccessAlgorithms and hardness results for happy coloring problems
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of happy edges. When we want to maximize the number of happy vertices, the problem is known as Maximum Happy Vertices (k-MHV). We further study the complexity of the problems and their weighted variants. For instance, we prove that for every k >= 3, both problems are NP-complete for bipartite graphs and k-MHV remains hard for split graphs. In terms of exact algorithms, we show both problems can be solved in time O*(2^n), and give an even faster O*(1.89^n)-time algorithm when k = 3. From a parameterized perspective, we give a linear vertex kernel for Weighted k-MHE, where edges are weighted and the goal is to obtain happy edges of at least a specified total weight. Finally, we prove both problems are solvable in polynomial-time when the graph has bounded treewidth or bounded neighborhood diversity.
- 9 December 2015
- Published by Springer Nature
- p. 424-438
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
- 9 December 2015
- Published by Springer Nature
- p. 424-438
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
- Open Access
Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$-free Edge Modification Problems
For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two non-edges and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Additionally, we prove that, these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.Open AccessParameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$-free Edge Modification Problems
For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two non-edges and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Additionally, we prove that, these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.