&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

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H ∈ F (where V (G) = V (H)), and an integer k, and the objective is to decide if there is a set S ⊆ V (G) of size at most k such that G − S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G ∈ F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of Ki,j-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0 &lt; &lt; 1, the family of graphs F, which comprise of graphs G such that |E(G)| ≤ |V (G)|2−, and show that F-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0 &lt; &lt; 1. © Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh.

World University root node

Department of Computer Science & Engineering

Leibniz International Proceedings in Informatics, LIPIcs

Conflict free feedback vertex set: A parameterized dichotomy

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.

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

Hitting and covering partially

The List Colouring Problem (LCP) is an NP-Hard optimization problem in which the goal is to find a proper list colouring of a graph G=(V, E) such that the number of colours used is minimized. This paper deals with the development and implementation of a Genetic Algorithm for the list colouring of graphs. Initial solutions are generated using two heuristics in equal proportion. Experiments have been carried out on randomly generated planar graphs with a list of colours for each vertex. Results for 32 graphs with size varying from 10 to 750 show that the proposed Genetic Algorithm implementation tends towards lower values of the number of colours used. © Springer Nature Singapore Pte Ltd. 2018.

Smart Innovation, Systems and Technologies

List colouring of graphs using a genetic algorithm

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

Vertex Separation Minimization Problem (VSMP) consists of finding a layout of a graph G = (V, E) which minimizes the maximum vertex cut or separation of a layout. It is an NP-complete problem in general for which metaheuristic techniques can be applied to find near optimal solution. VSMP has applications in VLSI design, graph drawing and computer language compiler design. VSMP is polynomially solvable for grids, trees, permutation graphs and cographs. Construction heuristics play a very important role in the metaheuristic techniques as they are responsible for generating initial solutions which lead to fast convergence. In this paper, we have proposed three construction heuristics H1, H2 and H3 and performed experiments on Grids, Small graphs, Trees and Harwell Boeing graphs, totaling 248 instances of graphs. Experiments reveal that H1, H2 and H3 are able to achieve best results for 88.71%, 43.5% and 37.1% of the total instances respectively while the best construction heuristic in the literature achieves the best solution for 39.9% of the total instances. We have also compared the results with the state-of-the-art meta-heuristic GVNS and observed that the proposed construction heuristics improves the results for some of the input instances. It was found that GVNS obtained best results for 82.9% instances of all input instances and the heuristic H1 obtained best results for 82.3% of all input instances. © 2017 Elsevier B.V.

Fulltext

Electronic Notes in Discrete Mathematics

Polynomial Time Efficient Construction Heuristics for Vertex Separation Minimization Problem

In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set S⊆ V(G) ∪ E(G) of cardinality at most k such that every element x∈ (V(G) ∪ E(G)) \ S is either adjacent to or incident with an element of S. We show that mds can be solved in time 7. 465 knO ( 1 ) on general graphs, and in time 2O(k)nO(1) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time 2 o ( k )nO ( 1 ) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP ⊆ NP/ poly. In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width tw, solves mds in time 6 twnO ( 1 ). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time O((2 - ϵ) tw ( G )nO ( 1 )) for any ϵ&gt; 0, where tw(G) is the tree-width of G. © 2017, Springer International Publishing AG.

Mixed dominating set: A parameterized perspective

Vertex Bisection Minimization problem (VBMP) consists of partitioning a vertex set into two sets B and B′ where |B|=|V|/2 such that vertex width, VW, is minimized which is defined as the number of vertices in B which are adjacent to at least one vertex in B′. It is an NP-complete problem in general. VBMP has applications in fault tolerance and is related to the complexity of sending messages to processors in interconnection networks via vertex disjoint paths. In this paper, a memetic algorithm has been designed for this problem (MAVBMP) in which four construction heuristics have been proposed to generate the initial population. These heuristics are analyzed statistically and accordingly used in proportion to generate the initial population for MAVBMP. A new crossover type search operator has been proposed for recombination and a local improvement operator has also been developed. Extensive experiments have been conducted on several classes of graphs such as complete bipartite graphs, 2-dimensional ordinary meshes, 2-dimensional toroidal meshes, 3-dimensional toroidal meshes, complete split graph, join of hypercubes and Harwell-boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for vertex width. © 2016 Elsevier Inc.

Information Sciences

On minimizing vertex bisection using a memetic algorithm

Vertex Bisection Minimization problem (VBMP) consists of partitioning a vertex set V of graph G = (V, E) into two sets B and B′ where ∣B∣ =⌊∣v∣/2⌋ such that vertex width (VW) is minimized where vertex width is defined as the number of vertices in B which are adjacent to at least one vertex in B′. It is an NP-complete problem in general. VBMP has applications in fault tolerance and is related to the complexity of sending messages to processors in interconnection networks via vertex disjoint paths. In this paper, we have proposed a new integer linear programming (ILP) and quadratically constrained quadratic programming (QCQP) formulation for VBMP. Both of them require number of variables and constraints lesser than existing ILPs and QCQP. We have also implemented ILP and obtained optimal results for various classes of graphs. The result of the experiments with the benchmark graphs shows that the proposed model outperforms the state of the art. Moreover, proposed model obtains optimal result for all the benchmark graphs. © 2016, Industrial Research Institute for Automation and Measurements. All rights reserved.