NAN. R. Aravind

N. R. Aravind

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Towards a conjecture on long induced rainbow paths in triangle-free graphs

    by N. R. Aravind, Shiwali Gupta, Rogers Mathew

    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.

  • Vertex partitioning problems on graphs with bounded tree width

    by N.R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare


  • Planar projections of graphs

    by N.R. Aravind, Udit Maniyar


  • Open Access

    An FPT algorithm for Matching Cut and d-cut

    by N R Aravind, Roopam Saxena

    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

    by N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang, Viresh Patel

    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$'.

  • Planar Projections of Graphs

    by N. R. Aravind, Udit Maniyar

  • Open Access

    Bipartitioning Problems on Graphs with Bounded Tree-Width

    by N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare

    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

    by N. R. Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, Juho Lauri

    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 Access

    Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$-free Edge Modification Problems

    by N. R. Aravind, R. B. Sandeep, Naveen Sivadasan

    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.