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

Given an undirected simple graph G, a set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. Such sets generalize vertex covers as a vertex cover is a 2-clique transversal. Perfect graphs are a well-studied class of graphs on which a minimum weight vertex cover can be obtained in polynomial time. Further, an r-clique transversal in a perfect graph is also a set of vertices whose deletion results in an (r- 1) -colorable graph. In this work, we study the problem of finding a minimum weight r-clique transversal in a perfect graph. This problem is known to be NP-hard for r≥ 3 and admits a straightforward r-approximation algorithm. We describe two different r+12-approximation algorithms for the problem. Both the algorithms are based on (different) linear programming relaxations. The first algorithm employs the primal–dual method while the second uses rounding based on a threshold value. We also show that the problem is APX-hard and describe hardness results in the context of parameterized algorithms and kernelization. © 2017, Springer Science+Business Media New York.

World University root node

Algorithmica

Approximability of Clique Transversal in Perfect Graphs

The separation dimension &amp;#x01d70b;π(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a k-degenerate graph on n vertices is O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension Ω(lg lg n). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n-vertex graphs with separation dimension s have at most 3(4 lg n)s−2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. © 2018 Wiley Periodicals, Inc.

Journal of Graph Theory

Separation dimension and sparsity

A linear ordering of the vertices of a graph Gseparates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges { a, b} and { c, d} of Gstrongly independent if the set of endpoints { a, b, c, d} induces a 2 K2 in G. The induced separation dimension of a graph G is the smallest cardinality of a family L of linear orders of V(G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in L. For each k∈ N, the family of graphs with induced separation dimension at most k is denoted by ISD (k). In this article, we initiate a study of this new dimensional parameter. The class ISD (1) or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in ISD (1) which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for ISD (1) is NP-complete for general graphs. Nevertheless, we show that the maximum induced matching problem can be solved efficiently in ISD (1). We then briefly study ISD (2) and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is Θ (lg n) and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. The second construction is also used to show that, for every k≥ 2 , the recognition problem for ISD (k) is NP-complete even on AT-free graphs. © 2017, Springer Science+Business Media, LLC.

The Induced Separation Dimension of a Graph

Large graphs are widely used in real world graph analytics. Memory available in a single machine is usually inadequate to process these graphs. A good solution is to use a distributed environment. Typical programming styles used in existing distributed environment frameworks are different from imperative programming and difficult for programmers to adapt. Moreover, some graph algorithms having a high degree of parallelism ideally run on an accelerator cluster. Error prone and lower level programming methods (memory and thread management) available for such systems repel programmers from using such architectures. Existing frameworks do not deal with the accelerator clusters. We propose a framework which addresses the previously stated deficiencies. Our framework automatically generates implementations of graph algorithms for distributed environments from the intuitive shared memory based code written in a high-level Domain Specific Language (DSL), Falcon. The framework analyses the intermediate representation, applies a set of optimizations and then generates Giraph code for a CPU cluster and MPI+OpenCL code for a GPU cluster. Experimental evaluations show efficiency and scalability of our framework. © Springer International Publishing AG, part of Springer Nature 2018.

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

Large scale graph processing in a distributed environment

In Software-Defined Networking (SDN), the importance of multi-controller operation is widely accepted mainly for 1) avoiding a single point of failure at the centralized SDN controller, and 2) scaling and load-balancing the control plane in large networks. Information exchange among SDN controllers is crucial for an end-to-end functioning of the routing and other applications like measurement and QoS. However, such information exchange introduces a scalability problem in the distributed architecture involving high communication overhead and long convergence time across the networks. The key concept of our solution against the problem is partitioning of the multi-controller SDN into the proper number of network chunks with the proper number of SDN controllers to operate in each chunk. This paper proposes VIBHAJAN, a control plane management mechanism 1) to find optimum groups of SDN controllers, 2) to isolate the information exchange within a logical boundary called Area, and 3) to enable information exchange between areas throughout the entire network. The implementation of VIBHAJAN currently facilitates a routing mechanism. The evaluation results show an approximate 50% reduction in communication overhead and 50% faster convergence compared to the broadcast-based multi-controller operation. Performance of the partitioning algorithm under different topologies is also shown. VIBHAJAN promises to facilitate a variety of network functions and applications over multi-controller SDN in a lightweight and scalable manner. © 2018 IEEE.

2018 IEEE Conference on Network Function Virtualization and Software Defined Networks, NFV-SDN 2018

VIBHAJAN: A Lightweight and Scalable Control Plane Management for Multi-Controller SDN

Due to intermittent connectivity among nodes in mobile opportunistic networks, the direct packet delivery strategy often experiences large delays. To alleviate this problem, nodes often pass a copy of their message to relay nodes, which in turn could deliver it to the destination. In this setting, we consider the problem of relay selection that minimizes the mean delivery delay. Applying ideas from a renewal theory, we derive a closed-form expression for the mean delivery delay in a heterogeneous network under any probabilistic two-hop relay selection policy. Utilizing this expression, a policy that assures the least mean delivery delay can be obtained as a solution of a linear program (the time complexity of mathcal O(n3). However, exploiting the structure of the mean delay minimization problem, we compute an optimal solution using an algorithm with linearithmic ( O(n log n)) time complexity. © 1997-2012 IEEE.

IEEE Communications Letters

Forwarding in heterogeneous mobile opportunistic networks

The boxicity of a graph G(V,E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in Rk. Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether the boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within O(n1−ϵ)-factor, for any ϵ&gt;0 in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time κ(n) factor approximation algorithm for computing boxicity and a κ(n)⌈loglogn⌉ factor approximation algorithm for computing the cubicity, where κ(n)=2nloglogn∕logn. These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question posed by Spinrad (2003) about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include O(κ(n)) factor approximation algorithms for computing the following parameters: the partial order dimension (poset dimension) of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, Ferrers dimension of digraphs and threshold dimension of split graphs and co-bipartite graphs. Each of these parameters is inapproximable within an O(n1−ϵ)-factor, for any ϵ&gt;0 in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems. We note that obtaining a o(n) factor approximation for poset dimension was also mentioned as an open problem by Felsner et al. (2017). In the second part of this paper, parameterized approximation algorithms for boxicity using various edit distance parameters are derived. We also present a parameterized approximation scheme for cubicity, using minimum vertex cover number as the parameter. © 2017 Elsevier B.V.

Fulltext

Discrete Applied Mathematics

Sublinear approximation algorithms for boxicity and related problems

The increasing demand for high-performance applications along with the advancement of technology, leading to power hungry manycore processors and rising chip temperature, have made the devices increasingly susceptible to wearout and aging resulting in early failure of the processing cores. The systemlevel analysis and optimization techniques offer a holistic view and ample opportunities to address lifetime reliability challenges, that can be explored and evaluated with the help of a fast and accurate simulation environment. This paper presents LifeSim, a simulation tool that integrates i) a state-of-The-Art manycore simulator, ii) a thermal simulator and iii) a lifetime reliability analyzer. The simulation tool is easily configurable without any code modification and compilation, with the help of a configuration file. To facilitate the development of solutions to mitigate aging and improve lifetime reliability, we enhanced the simulator with scheduling and frequency control features. It offers both preemptive and non-preemptive scheduling along with an interface for dynamic voltage frequency scaling (DVFS). Further, it logs statistics such as power, temperature, aging, and mean time to failure (MTTF) and also generates graphs for visualization and easy comparison of the performance of the solution adopted by the user. © 2018 IEEE.

2018 IEEE 8th Annual Computing and Communication Workshop and Conference, CCWC 2018

LifeSim: A lifetime reliability simulator for manycore systems

The vertical interplay among Edge-Fog-Cloud computing introduces a new requirement to accommodate services, network functions and chains of them in a heterogeneous environment. However, such operation involves challenging tasks including management of resource availability, compliance with Service Level Agreements (SLAs), dynamic re-configuration of services and networks across different computing domains. This paper proposes Dynamic Network Function (DNF) that involves 1) a tractable VNF placement algorithm, and 2) a bottleneck detection and removal algorithm for the heterogeneous computing and network environments representing the Edge-Fog-Cloud interplay. The proof of concept (PoC) implementation of DNF has been done using Docker-based NFV and SDN setups as well as a simulation setup for studying the DNF scalability. The evaluation results showed that DNF could achieve high acceptance ratio of SLA requests with reasonably short duration. The PoC implementation also exhibited the proper functions to 1) orchestrate the NFV and SDN, and 2) detect and mitigate the bottlenecks. © 2018 Association for Computing Machinery.

Asian Internet Engineering Conference, AINTEC 2018

Dynamic Network Function (DNF): Service chain placement and bottleneck removal for edge-fog-cloud interplay

Adaptive video streaming improves users' quality of experience (QoE), while using the network efficiently. In the last few years, adaptive video streaming has seen widespread adoption and has attracted significant research effort. We study a dynamic system of random arrivals and departures for different classes of users using the adaptive streaming industry standard DASH (Dynamic Adaptive Streaming over HTTP). Using a Markov chain based analysis, we compute the user QoE metrics: probability of starvation, prefetching delay, average video quality and switching rate. We validate our model by simulations, which show a very close match. Our study of the playout buffer is based on client adaptation scheme, which makes efficient use of the network while improving users' QoE. We prove that for buffer-based variants, the average video bit-rate matches the average channel rate. Hence, we would see quality switches whenever the average channel rate does not match the available video bit rates. We give a sufficient condition for setting the playout buffer threshold to ensure that quality switches only between adjacent quality levels. © 2018 IFIP.