Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

We study the parameterized complexity of various graph theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties. In real world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the DynamicΠ -Deletion problem which is the dynamic variant of the classical Π -Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of DynamicΠ -Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved algorithms and linear kernels. Specifically, we show that Dynamic Vertex Cover has a deterministic algorithm with 1. 0822 knO ( 1 ) running time and Dynamic Feedback Vertex Set has a randomized algorithm with 1. 6667 knO ( 1 ) running time. We also show that Dynamic Connected Feedback Vertex Set can be solved in 2 O ( k )nO ( 1 ) time. For each of Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set, we describe an algorithm with 2 knO ( 1 ) running time and show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture. © 2017, Springer Science+Business Media, LLC.

Department of Computer Science and Engineering

World University root node

Fulltext

Algorithmica

Dynamic Parameterized Problems

In this work, we study the parameterized complexity of various classical graph-theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties that are of interest to us. In real-world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the Dynamic Pi-Deletion problem which is the dynamic variant of the Pi-Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of Dynamic Pi-Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved FPT algorithms and give linear kernels. Specifically, we show that Dynamic Vertex Cover admits algorithms with running times 1.1740^k*n^{O(1)} (polynomial space) and 1.1277^k*n^{O(1)} (exponential space). Then, we show that Dynamic Feedback Vertex Set admits a randomized algorithm with 1.6667^k*n^{O(1)} running time. Finally, we consider Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set and describe algorithms with 2^k*n^{O(1)} running time improving over the known running time bounds for these problems. Additionally, for Dynamic Dominating Set and Dynamic Connected Dominating Set, we show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture.

Leibniz International Proceedings in Informatics, LIPIcs

Dynamic Parameterized Problems

A class domination coloring (also called as cd-coloring) of a graph is a proper coloring such that for every color class, there is a vertex that dominates it. The minimum number of colors required for a cd-coloring of the graph G, denoted by χcd(G), is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q, can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q? For the first problem, we give an exact algorithm with running time O(2nn4 log n). Also, we show that the problem is FPT with respect to the number of colors q as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O(q3) vertices. For the second (deletion) problem, we show NP-hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP-hard if q is a part of the input and FPT with respect to k and q. As recognizing graphs with cd-chromatic number at most q is NP-hard in general for q ≥ 4, the deletion problem is unlikely to be FPT when parameterized by the size of deletion set on general graphs. We show fixed parameter tractability for q ∈ {2, 3} using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. © Springer International Publishing AG 2017.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Parameterized and exact algorithms for class domination coloring

We study some well-known graph contraction problems in the recently introduced framework of lossy kernelization. In classical kernelization, given an instance (I, k) of a parameterized problem, we are interested in obtaining (in polynomial time) an equivalent instance (I′, k′) of the same problem whose size is bounded by a function in k. This notion however has a major limitation. Given an approximate solution to the instance (I′, k′), we can say nothing about the original instance (I, k). To handle this issue, among others, the framework of lossy kernelization was introduced. In this framework, for a constant α, given an instance (I, k) we obtain an instance (I′, k′) of the same problem such that, for every c &gt; 1, any c-approximate solution to (I′, k′) can be turned into a (cα)-approximate solution to the original instance (I, k) in polynomial time. Naturally, we are interested in a polynomial time algorithm for this task, and further require that |I′|+k′ = kO(1). Akin to the notion of polynomial time approximation schemes in approximation algorithms, a parameterized problem is said to admit a polynomial size approximate kernelization scheme (PSAKS) if it admits a polynomial size α-approximate kernel for every approximation parameter α &gt; 1. In this work, we design PSAKSs for TREE CONTRACTION, STAR CONTRACTION, OUT-TREE CONTRACTION and CACTUS CONTRACTION problems. These problems do not admit polynomial kernels, and we show that each of them admit a PSAKS with running time kf(α)|I|O(1) that returns an instance of size kg(α) where f(α) and g(α) are constants depending on α. © R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale.

Lossy kernels for graph contraction problems

Given an undirected simple graph G, a subset T of vertices is an r-clique transversal if it has at least one vertex from every r-clique in G. I.e. T is an r-clique transversal if G-S is K r -free. r-clique transversals generalize vertex covers as a vertex cover is a set of vertices whose deletion results in a graph that is K 2-free. Perfect graphs are a well-studied class of graphs on which a minimum vertex cover can be obtained in polynomial time. However, the problem of finding a minimum r-clique transversal is NP-hard even for r=3. As any induced odd length cycle in a perfect graph is a triangle, a triangle-free perfect graph is bipartite. I.e. in perfect graphs, a 3-clique transversal is an odd cycle transversal. In this work, we describe an(r+1/2) -approximation algorithm for r-clique transversal on weighted perfect graphs improving on the straightforward r-approximation algorithm. We then show that 3-Clique Transversal is APX-hard on perfect graphs and it is NP-hard to approximate it within any constant factor better than 4/3 assuming the unique games conjecture. We also show intractability results in the parameterized complexity framework. © 2014 Springer-Verlag Berlin Heidelberg.

LP approaches to improved approximation for clique transversal in perfect graphs

A graph is k-chordal if it has no induced cycle of length greater than k. We give a new characterization of k-chordal graphs that generalizes the well-known characterization of chordal graphs by Dirac in terms of simplicial vertices and simplicial orderings. © 2013 Elsevier B.V. All rights reserved.

Discrete Mathematics

A Dirac-type characterization of k-chordal graphs

Given a graph G and an odd cycle transversal T, we describe an elegant O* (2|T|) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe that our algorithm, based on a reduction to VERTEX Cover, is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between ODD CYCLE TRANSVERSAL and VERTEX COVER. © 2013 Elsevierc B.V. All rights reserved.

Information Processing Letters

Another disjoint compression algorithm for odd cycle transversal

We consider the (r, l)-Partization problem of finding a set of at most k vertices whose deletion results in a graph that can be partitioned into r independent sets and l cliques. Restricted to perfect graphs and split graphs, we describe sequacious fixed-parameter tractability results for (r, 0)-Partization, parameterized by k and r. For (r, l)-Partization where r+l = 2, we describe an O*(2k) algorithm for perfect graphs. We then study the parameterized complexity hardness of a generalization of the Above Guarantee Vertex Cover by a reduction from (r, l)-Partization.

Journal of Graph Algorithms and Applications

Parameterized algorithms for (r, l)-Partization

Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover defined as: Given a graph G, a clique cover K of G and a non-negative integer k, does G have a vertex cover of size at most k +Σ CεK(|C| - 1)? We study the parameterized complexity hardness of this problem by a reduction from r-Partization. We then describe sequacious fixed-parameter tractability results for r-Partization, parameterized by the solution size k and the required chromaticity r, in perfect graphs and split graphs. For Odd Cycle Transversal, we describe an O*(2 k) algorithm for perfect graphs and a polynomial-time algorithm for co-chordal graphs. © 2012 Springer-Verlag.