Hitting set for hypergraphs of low VC-dimension
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Brönnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.
Budgeted Dominating Sets in Uncertain Graphs
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph G = (V,E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1. We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is W[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in no(k) time. 2. We show that if one is willing to settle for (1 ) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3. We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is W[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4. Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset ΣΠ Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.
Succinct Data Structure for Path Graphs
We consider the problem of designing space-efficient data structures for unlabelled path graphs with n vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies nlog n+o(nlog n) bits while answering adjacency query in O(log n) time, and neighborhood and degree queries in O(dlog2n) time where d is the degree of the queried vertex. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes O(nlog2n) bits while answering adjacency and degree queries in constant time and neighborhood query in O(dlog n) time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.
A novel data structure for biconnectivity, triconnectivity, and κ-tree augmentation
For a connected graph, a subset of vertices of least size whose deletion increases the number of connected components is the vertex connectivity of the graph. A graph with vertex connectivity κ is said to be κ-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (κ + 1)-vertex connected. In this paper, we report our study of connectivity augmentation in 1-connected graphs, 2-connected graphs, and κ- trees. For a graph, our data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of an associated tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure we present a new combinatorial analysis and an elegant proof of correctness of our linear time algorithm for optimum connectivity augmentation. While this is the first attempt on the study of k-tree augmentation, the study on other two augmentations is reported in the literature. Compared to other augmentations reported in the literature, we avoid recomputation of the associated tree by maintaining the data structure under edge additions. Copyright © 2011, Australian Computer Society, Inc.
LP can be a cure for Parameterized Problems
We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181r) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O *(f(k)) for a time complexity of the form O(f(k)n O(1)), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181k) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION and ALMOST 2-SAT, and an O *(1.6181k) algorithm for KON̈IG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices. © N.S. Narayanaswamy, V. Raman, M.S. Ramanujan, and S. Saurabh.
Effective Parallelization of the Vehicle Routing Problem
Capacitated Vehicle Routing Problem (CVRP) is an important combinatorial optimization problem, which is also NP-hard. A wide array of heuristics have been proposed in the literature to obtain an approximate solution to CVRP. To improve the execution time, parallel methods have been developed for accelerating metaheuristics-based algorithms, genetic algorithms, and evolutionary algorithms for CVRP. Despite these advances, our experiments with the state-of-The-Art parallel solutions indicate that their run times are too high to be practically useful. The combinatorial explosion is so high that the execution time is prohibitively large even on mid-sized CVRP instances having a few hundred customers. In this work, we propose a novel technique which combines local search and randomization for solving CVRP faster with reasonable accuracy, even on large problem instances. Our usage of randomization enables searching a large space of candidate solutions. We experimentally compare our proposed method with the state-of-The-Art GPU implementations on diverse input instances and demonstrate the efficacy of our approach. Our sequential and shared-memory parallel implementations are on an average 36-1189× faster than the state-of-The-Art GPU-parallel genetic algorithms while also achieving a superior solution quality. Furthermore, our reported solutions are close to the current best-known solutions from CVRPLIB.
On the complexity landscape of connected f-factor problems
Given an n-vertex graph G and a function f : V (G) → {0, . . . , n-1}, an f-factor is a subgraph H of G such that degH(v) = f(v) for every vertex v ϵ V (G); we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least nϵ for each vertex v and ϵ < 1; on the other side of the spectrum, the problem was known to be polynomial-time solvable when f(v) is at least n3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restricting the function f. In particular, we show that when f(v) is required to be at least n/(log n)c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1. We also show that when c > 1, the problem is NP-intermediate.
Algorithms for satisfiability using independent sets of variables
An independent set of variables is one in which no two variables occur in the same clause in a given instance of k-SAT. Instances of k-SAT with an independent set of size i can be solved in time, within a polynomial factor of 2n-i. In this paper, we present an algorithm for k-SAT based on a modification of the Satisfiability Coding Lemma. Our algorithm runs within a polynomial factor of 2(n-i)(1-1/2k-2), where i is the size of an independent set. We also present a variant of Schöning's randomized local-search algorithm for k-SAT that runs in time which is with in a polynomial factor of (2k-3/k-1)n-i. © Springer-Verlag Berlin Heidelberg 2005.
Hybrid genetic algorithm for ridesharing with timing constraints: Efficiency analysis with real-world data
Ridesharing is an effective, affordable and environment-friendly way of transportation. This paper proposes a Hybrid Genetic Algorithm(HGA) using elements from Simulated Annealing(SA) and Local search(LS) which is very suitable for Ridesharing related applications. The designed algorithm efficiently handles advanced constraints like timing windows for pick-up, detour time(or distance), and waiting-time minimization. To quantify the effectiveness of HGA for the Ridesharing problem, we study Ridesharing as a close variant of the Orienteering Problem(OP) and Orienteering Problem with Time Windows(OPTW). Both these problems have been extensively studied and have many benchmark data sets. The experiments performed on popular benchmark instances of orienteering problems show that HGA for orienteering problems outperforms all the available algorithms in the literature. Further, for many of the instances, our HGA has discovered solutions that are better than the current Best Known solutions. Using our HGA for orienteering problems, we have developed a prototype system for Ridesharing. The experiments using real-world New York taxi trip data [19] shows that the system ensures that about 40%-50% of the rides could have been shared, and 60%-70% of customers could have shared rides. The detailed data analysis shows how to tune the parameters for the system to achieve the best possible performance.
Planning for the convoy movement problem
Convoy movement problem has significant practical applications. The problem has been attempted in many styles with varying results. We address it as an AI Search and Planning and Scheduling problem. The work focuses on modeling the convoy movement problem using PDDL and attempting a solution using existing planning methods and planners. Initial results indicated problems of scalability. To address this we propose a two stage planning process.