&ldquo;IIT Jodhpur is committed to impart quality education to facilitate the creation of qualified, competent and responsible human resources to meet the emerging technological challenges of the world. It is working towards creating an equitable learning platform that is positive, accessible and effective in the face of the modern societal and scientific advancements.

Flexibility in curriculum, in all its academic programs, encompassing elements of teaching, research, creativity, innovation and entrepreneurship is the most unique feature of IIT Jodhpur. The Department of Science and Technology (DST), under the National Mission on Cyber Physical Systems, has identified IIT Jodhpur as a Technology &amp; Innovation Hub in the area of Augmented Reality and Virtual Reality. The institute has also been nominated as the coordinator for the Jodhpur City and Knowledge Cluster by the Office of Principal Scientific Adviser, Government of India.

The sprawling 852-acre IIT Jodhpur campus is a majestic tribute to the deep-rooted diverse cultural heritage of the region. The campus is an architectural masterpiece, which is slated to become an international exemplar of sustainability with net-zero energy, and advanced water and waste management strategies.&rdquo;

IIT Jodhpur

d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial d -HS) and Partial d -Exact Set Cover (Partial d -Exact SC), respectively. In Partial d -HS, given a universe U, a family F, of sets of size at most d over U, and integers k and t, the objective is to decide if there exists a (Formula Presented) of size at most k such that S intersects with at least t sets in F. We obtain a kernel for Partial d -HS in which the size of the universe is bounded by O(dt) and the size of the family is bounded by O(dt2). Using this result, we obtain a kernel for Partial Vertex Cover (PVC) with O(t) vertices, where t is the number of edges to be covered. Next, we study the Partial d -Exact SC problem, where, given a universe U, a family F, of sets of size exactly d over U, and integers k and t, the objective is to decide if there is (Formula Presented) of size at most k, such that S covers at least t elements in U. We design a kernel for Partial d -Exact SC in which sizes of the universe and the family are bounded by (Formula Presented). Finally, we study a special case of Partial d -HS, when d=2, and design an exact exponential time algorithm with running time (Formula Presented). © 2018, Springer International Publishing AG, part of Springer Nature.

World University root node

Department of Computer Science & Engineering

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

Hitting and covering partially

Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S is in π. In this paper, we introduce the conflict free version of this classical problem, namely Conflict Free π-Vertex Deletion (CF-π-VD), and study these problems from the viewpoint of classical and parameterized complexity. In the CF-π-VD problem, given two graphs G and H on the same vertex set and a positive integer k, the objective is to determine whether there exists a set S ⊑ V(G), of size at most k, such that G − S is in π and H[S] is edgeless. Initiating a systematic study of these problems is one of the main conceptual contribution of this work. We obtain several results on the conflict free version of several classical problems. Our first result shows that if π is characterized by a finite family of forbidden induced subgraphs then CF-π-VD is Fixed Parameter Tractable (FPT). Furthermore, we obtain improved algorithms for conflict free version of several well studied problems. Next, we show that if π is characterized by a “well-behaved” infinite family of forbidden induced subgraphs, then CF-π-VD is W[1]-hard. Motivated by this hardness result, we consider the parameterized complexity of CF-π-VD when H is restricted to well studied families of graphs. In particular, we show that the conflict free versions of several well-known problems such as Feedback Vertex Set, Odd Cycle Transversal, Chordal Vertex Deletion and Interval Vertex Deletion are FPT when H belongs to the families of d-degenerate graphs and nowhere dense graphs. © 2018, Springer International Publishing AG, part of Springer Nature.

Conflict free version of covering problems on graphs: Classical and parameterized

In the last few years, parameterized complexity has emerged as a new tool to analyze the running time of randomized local search algorithm. However, such analysis are few and far between. In this paper, we do a parameterized running time analysis of a randomized local search algorithm and a (1+1) EA for a classical graph partitioning problem, namely, Max l-Uncut, and its balanced counterpart Max Balanced l-Uncut. In Max l-Uncut, given an undirected graph G = (V, E), the objective is to find a partition of V(G) into l parts such that the number of uncut edges - edges within the parts - is maximized. In the last few years, Max l-Uncut and Max Balanced l-Uncut are studied extensively from the approximation point of view. In this paper, we analyze the parameterized running time of a randomized local search algorithm (RLS) for Max Balanced l-Uncut where the parameter is the number of uncut edges. RLS generates a solution of specific fitness in polynomial time for this problem. Furthermore, we design a fixed parameter tractable randomized local search and a (1 + 1) EA for Max l-Uncut and prove that they perform equally well. © 2018 Copyright held by the owner/author(s).

GECCO 2018 Companion - Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion

A parameterized runtime analysis of randomized local search and evolutionary algorithm for max l-uncut

For a family of graphs (formula presented), the (formula presented) -Contraction problem takes as an input a graph G and an integer k, and the goal is to decide whether there exists (formula presented) of size at most k such that G/F belongs to (formula presented). When (formula presented) is the family of paths, trees or cacti, then the correspond-ing problems are Path Contraction, Tree Contraction and Cac-tus Contraction, respectively. It is known that Tree Contraction and Cactus Contraction do not admit a polynomial kernel unless (formula presented), while Path Contraction admits a kernel with O(k) vertices. The starting point of this article are the following natural ques-tions: What is the structure of the family of paths that allows Path Con-traction to admit a polynomial kernel? Apart from the size of the solu-tion, what other additional parameters should we consider so that we can design polynomial kernels for these basic contraction problems? With the goal of designing polynomial kernels, we consider the family of trees with bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction (Bounded TC). Here, an input is a graph G, integers k and, (formula presented) and the goal is to decide whether or not, there exists a subset (formula presented) of size at most k such that G/F is a tree with at most leaves. We design a kernel for Bounded TC with O(k) vertices and (formula presented) edges. Finally, we study Bounded Cactus Contraction (Bounded CC) which takes as input a graph G and integers k and. The goal is to decide whether there exists a subset (formula presented) of size at most k such that G/F is a cactus graph with at most (formula presented) leaf blocks in the corresponding block decomposi-tion. For Bounded CC we design a kernel with (formula presented) vertices and (formula presented) edges. We complement our results by giving kernelization lower bounds for Bounded TC, Bounded OTC and Bounded CC by showing that unless (formula presented) the size of the kernel we obtain is optimal. © Springer International Publishing AG 2017.