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

The boxicity (resp. cubicity) 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 (resp. cubes) in Rk. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n1-ε)-factor for any ε&gt;0 in polynomial time, unless NP=ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n1-ε-factor approximation algorithm for computing boxicity in polynomial time, for any ε&gt;0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs - intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Ω(n). We give a (2+1/k)-factor (resp.(2+ logn/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k≥1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn+n2) in both these cases, and in O(mn+kn2)=O(n3) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. © 2014 Elsevier Ltd. All rights reserved.

World University root node

Discrete Applied Mathematics

A constant factor approximation algorithm for boxicity of circular arc graphs

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) ≤ 2r(G) + c, where r(G) denotes the radius of G and c ∈ {0, 1 ,2}. In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time (Formula presented.)-factor approximation algorithms. © 2013, Springer Japan.

Fulltext

Graphs and Combinatorics

Rainbow Connection Number of Graph Power and Graph Products

We study the performance of the Metropolis algorithm for the problem of finding a code word of weight less than or equal to M, given a generator matrix of an [n; κ]-binary linear code. The algorithm uses the set Sκ of all κ × κ invertible matrices as its search space where two elements are considered adjacent if one can be obtained from the other via an elementary row operation (i.e by adding one row to another or by swapping two rows.) We prove that the Markov chains associated with the Metropolis algorithm mix rapidly for suitable choices of the temperature parameter T. We ran the Metropolis algorithm for a number of codes and found that the algorithm performed very well in comparison to previously known experimental results. © 2014 ACM.

GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

Performance of metropolis algorithm for the minimum weight code word problem

In this article, we study the problem of how to maximize the throughput of a periodic real-time system under a given peak temperature constraint.We assume that different tasks in our system may have different power and thermal characteristics. Two scheduling approaches are presented. The first is built upon processors that can be in either active or sleep mode. By judiciously selecting tasks with different thermal characteristics as well as alternating the processor's active/sleep mode, the sleep period required to cool down the processor is kept at aminimum level, and, as the result, the throughput ismaximized.We further extend this approach for processors with dynamic voltage/frequency scaling (DVFS) capability. Our experiments on a large number of synthetic test cases as well as real benchmark programs show that the proposed methods not only consistently outperform the existing approaches in terms of throughput maximization, but also significantly improve the feasibility of tasks when a more stringent temperature constraint is imposed. © 2014 ACM.

Transactions on Embedded Computing Systems

Throughput maximization for periodic real-time systems under the maximal temperature constraint

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.

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

LP approaches to improved approximation for clique transversal in perfect graphs

Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n) = 1 and t(n) = n!. For n odd, we prove (nφ(n))=2k ≥ s(n) ≥ n!-2-(n-1)=2 ((n-1)=2)! and 2(n-1)=2 - ( n-1 2 )! ≥ t(n) - 2k - (n - 1)!=φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function. © 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.

Discrete Mathematics and Theoretical Computer Science

On Additive Combinatorics of Permutations of ℤn

A family F of permutations of the vertices of a hypergraph H is called pairwise suitable for H if, for every pair of disjoint edges in H, there exists a permutation in F in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for H is called the separation dimension of H and is denoted by π(H). Equivalently, π(H) is the smallest natural number k so that the vertices of H can be embedded in ℝk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. © Springer International Publishing Switzerland 2014.

Boxicity and separation dimension

In this article, we formulate and study quantum analogues of randomized search heuristics, which make use of Grover search (in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212-219. ACM, New York, 1996) to accelerate the search for improved offsprings. We then specialize the above formulation to two specific search heuristics: Random Local Search and the (1+1) Evolutionary Algorithm. We call the resulting quantum versions of these search heuristics Quantum Local Search and the (1+1) Quantum Evolutionary Algorithm. We conduct a rigorous runtime analysis of these quantum search heuristics in the computation model of quantum algorithms, which, besides classical computation steps, also permits those unique to quantum computing devices. To this end, we study the six elementary pseudo-Boolean optimization problems OneMax, LeadingOnes, Discrepancy, Needle, Jump, and TinyTrap. It turns out that the advantage of the respective quantum search heuristic over its classical counterpart varies with the problem structure and ranges from no speedup at all for the problem Discrepancy to exponential speedup for the problem TinyTrap. We show that these runtime behaviors are closely linked to the probabilities of performing successful mutations in the classical algorithms. © 2013 Springer Science+Business Media New York.

Algorithmica

Evolutionary algorithms for quantum computers

Let n,r,k be positive integers such that 3≤k&lt;n and 2≤r≤k-1. Let m(n,r,k) denote the maximum number of edges an r-uniform hypergraph on n vertices can have under the condition that any collection of i edges spans at least i vertices for all 1≤i≤k. We are interested in the asymptotic nature of m(n,r,k) for fixed r and k as n→∞. This problem is related to the forbidden hypergraph problem introduced by Brown, Erdos, and Sós and very recently discussed in the context of combinatorial batch codes (CBCs). In this short paper we obtain the following results. Using a result due to Erdos we are able to show m(n,r,k)=o(nr) for 7≤k, and 3≤r≤k-1- ⌈logk⌉. This result is best possible with respect to the upper bound on r as we subsequently show through explicit construction that for 6≤k, and k-⌈logk⌉≤r≤k-1,m(n,r,k)=Θ(nr).This explicit construction improves on the non-constructive general lower bound obtained by Brown, Erdos, and Sós for the considered parameter values.For 2-uniform CBCs we obtain the following results. We provide exact value of m(n,2,5) for n≥5.Using a result of Lazebnik et al. regarding maximum size of graphs with large girth, we improve the existing lower bound on m(n,2,k) (Ω(n k+1/k-1)) for all k≥8 and infinitely many values of n.We show m(n,2,k)=O(n1 + 1/⌊k/4⌋) by using a result due to Bondy and Simonovits, and also show m(n,2,k)=Θ(n3/2) for k=6,7,8 by using a result of Kovári, Sós, and Turán. © 2013 Elsevier B.V. All rights reserved.

On an extremal hypergraph problem related to combinatorial batch codes

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl [1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. © 2014 Elsevier B.V.