Department of Computer Science and Engineering

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.

World University root node

Fulltext

Algorithmica

Dynamic Parameterized Problems

A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. It is known that, unless P=NP, the rainbow connection number of a graph cannot be approximated in polynomial time to a multiplicative factor less than 5/4, even when the input graph is chordal [Chandran and Rajendraprasad, FSTTCS 2013]. In this article, we determine the computational complexity of the above problem on successively more restricted graph classes, viz.: split graphs and threshold graphs. In particular, we establish the following: 1. The problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k∈{2,3}, but can be solved in polynomial time for all other values of k. Furthermore, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum.2. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Furthermore, we can optimally rainbow colour a threshold graph in linear time. © 2015 Elsevier B.V.

Discrete Applied Mathematics

Rainbow colouring of split graphs

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f : f1 ng R of length n contains a pattern 2 Sk (Sk is the group of permutations of k elements), i there are indices i1 < i2 ik, such that f(ix) > f(iy) whenever π (x) > π (y). If f does not containwe say f is free. For example, for (2; 1), the property of being free is equivalent to being non-decreasing, i.e. monotone. The property of being (k; k 1 1) free is equivalent to the property of having a partition into at most k 1 non-decreasing subsequences. Let 2 Sk, k constant, be a (forbidden) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that is free from the case that f diffiers in more than en places from any free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i.e., (k; k 1 1) and (1; 2k), we design non-adaptive one-sided error tests of (1 log n)O(k2) query complexity. For non-monotone patterns, we show that for any size-k non-monotone any non-adaptive one-sided error test requires at least (p n) queries. This general lower bound can be further strengthened for specific non-monotone k-length patterns to (n12=(k+1)). On the other hand, there always exists a non- Adaptive one-sided error test for 2 Sk with O(1=kn11=k) query complexity. Again, this general upper bound can be further strengthened for specific non-monotone patterns. for Department of Computer Science, University of Haifa, Israel. Department of Computer Science, University of Haifa, Israel. Department of Computer Science, Indian Institute of Technology Palakkad, India. (Work done while visiting the Caesarea Rothschild Institute, University of Haifa.) xDepartment of Computer Science, TU Dortmund, Germany. (The author acknowledges the support of ERC grant 307696.) (1; 3; 2), we describe an test with (almost tight) query complexity of eO( p n). Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any 2 S3, tests freeness by making (1 log n)O(1) queries. For all algorithms presented here, the running times are linear in their query complexity. Copyright © by SIAM.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Testing for forbidden order patterns in an array

On-chip trace buffers are increasingly being used for at-speed debug during postsilicon validation. The limited size of these buffers results in their frequent overflowing. In scenarios when such overflowing is not desirable, the chip is stalled, and the state data recorded in these buffers are transferred off-chip. Such frequent stalling significantly impedes efficient debugging. We propose a novel scheme to minimize the number of such stalls using a portion of the trace buffer to also store summaries of trace messages. We describe an overlapped trace buffer architecture that uses a reduced number of ports to capture tapered summaries where both detailed and summary versions of traces are stored simultaneously. We propose a simple hardware structure to generate two kinds of trace summaries-spatial and temporal-as specified by the validation engineer. We introduce a storage specification language that allows the validation engineer to unambiguously specify the information to be captured in these summaries to the debug hardware. We demonstrate that our proposal significantly reduces the number of stalls for off-chip transfer of captured traces in four bug scenarios that are representative of different classes of bugs encountered during postsilicon validation. © 2017 IEEE.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems

Managing trace summaries to minimize stalls during postsilicon validation

Indian Institute of Science Bangalore

Falcon:-A Graph Manipulation Language for Distributed Heterogeneous Systems

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

In this work, we completely characterize (1) permutation binomials of the form x2n-12t-1+1+ax∈F2n[x],n=2st,a∈F22t∗, and (2) permutation trinomials of the form x2s+1+x2s-1+1+αx∈F2t[x], where s, t are positive integers. The first result, which was our primary motivation, is a consequence of the second result. The second result may be of independent interest. © 2016, Springer Science+Business Media New York.

Designs, Codes, and Cryptography

On some permutation binomials and trinomials over F2n

Graph models of social information systems typically contain trillions of edges. Such big graphs cannot beprocessed on a single machine. The graph object must bepartitioned and distributed among machines and processedin parallel on a computer cluster. Programming such systemsis very challenging. In this work, we present DH-Falcon, a graph DSL (domain-specific language) which can be usedto implement parallel algorithms for large-scale graphs, tar-geting Distributed Heterogeneous (CPU and GPU) clusters. DH-Falcon compiler is built on top of the Falcon compiler, which targets single node devices with CPU and multipleGPUs. An important facility provided by DH-Falcon is that itsupports mutation of graph objects, which allows programmerto write dynamic graph algorithms. Experimental evaluationshows that DH-Falcon matches or outperforms state-of-The-Art frameworks and gains a speedup of up to 13×. © 2017 IEEE.

Proceedings - IEEE International Conference on Cluster Computing, ICCC

DH-Falcon: A Language for Large-Scale Graph Processing on Distributed Heterogeneous Systems

Campaigners, advertisers, and activists are increasingly turning to social recommendation mechanisms, provided by social media, for promoting their products, services, brands, and even ideas. However, many a time, such social network-based campaigns perform poorly in practice, because the intensity of recommendations drastically reduces beyond a few hops from the source. A natural strategy for maintaining the intensity is to provide incentives. In this paper, we address the problem of minimizing the cost incurred by the campaigner for incentivizing a fraction of individuals in the social network, while ensuring that the campaign message reaches a given expected fraction of individuals. We also address the dual problem of maximizing the campaign penetration for a resource constrained campaigner. To help us understand and solve the above-mentioned problems, we use percolation theory to formally state them as optimization problems. These problems are not amenable to traditional approaches because of a fixed point equation that needs to be solved numerically. However, we use results from reliability theory to establish some key properties of the fixed point, which in turn enables us to solve these problems using algorithms that are linearithmic in maximum node degree. Furthermore, we evaluate the efficacy of the analytical solutions by performing simulations on real-world networks. © 2017 IEEE.

IEEE/ACM Transactions on Networking

Incentivized campaigning in social networks

In this paper, we present a generic controller that ensures fair and efficient operation of IEEE 802.11 infrastructure wireless local area networks (WLANs) with multiple co-channel access points. Our controller addresses performance issues of long-lived TCP transfers in multi-AP WLANs, by overlaying a coarse time-slicing scheduler on top of a cascaded fair queuing scheduler. The time slices and queue weights, used in our controller, are obtained from the solution of a constrained utility optimization formulation. A study of the impact of coarse time-slicing on TCP is also presented in this paper. We also present a methodology to improve the performance of co-existing short-lived and interactive TCP flows. Finally, we report the results of experiments performed on a real testbed, demonstrating the efficacy of our controller. © 2017 Elsevier Ltd