Computer Science and Engineeringhttp://repository.iitgn.ac.in/handle/123456789/4272018-05-27T03:18:00Z2018-05-27T03:18:00ZGeneric Single Edge Fault Tolerant Exact Distance OracleGupta, ManojSingh, Aditihttp://repository.iitgn.ac.in/handle/123456789/36712018-05-15T10:46:18Z2018-05-01T00:00:00ZGeneric Single Edge Fault Tolerant Exact Distance Oracle
Gupta, Manoj; Singh, Aditi
Given an undirected unweighted graph G and a source set S of |S|=? sources, we want to build a data structure which can process the following query {\sc Q}(s,t,e): find the shortest distance from s to t avoiding an edge e, where s?S and t?V. When ?=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n2) space (O~(?) hides poly logn factor.) and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{\`o} et. al. (STACS 2018) designed a data-structure of size O~(?1/2n3/2) with the query time of O(n?????) for the above problem. We improve their result by designing a data-structure of size O~(?1/2n3/2) that can answer queries in O~(1) time. In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of the {\em replacement} paths ending at a vertex t are disjoint, then the number of such paths is O(n?????). This eventually gives a bound of O(nn?????)=O(?1/2n3/2) for their problem. {\em Disjointness of detours} is a very crucial property used in the above result. We show a similar result for a subset of replacement path which \textbf{may not} be disjoint. This result is the crux of our paper and may be of independent interest.?
2018-05-01T00:00:00ZFully dynamic maximal matching in O(log N) update timeBaswana, SurenderGupta, ManojSen, Sandeephttp://repository.iitgn.ac.in/handle/123456789/36552018-05-15T10:39:50Z2018-01-01T00:00:00ZFully dynamic maximal matching in O(log N) update time
Baswana, Surender; Gupta, Manoj; Sen, Sandeep
We present an algorithm for maintaining a maximal matching in a graph under
addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n)
time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence
of t edge updates, the total time taken by the algorithm is O(tlog n + n log2 n) with high probability
2018-01-01T00:00:00ZSimple dynamic algorithms for Maximal Independent Set and other problemsGupta, ManojKhan, Shahbazhttp://repository.iitgn.ac.in/handle/123456789/36262018-04-18T12:11:17Z2018-04-01T00:00:00ZSimple dynamic algorithms for Maximal Independent Set and other problems
Gupta, Manoj; Khan, Shahbaz
2018-04-01T00:00:00ZComplexity of manipulation with partial information in votingDeya, PalashMisra, NeeldharaNarahari, Y.http://repository.iitgn.ac.in/handle/123456789/35802018-04-10T10:04:19Z2018-03-01T00:00:00ZComplexity of manipulation with partial information in voting
Deya, Palash; Misra, Neeldhara; Narahari, Y.
The Coalitional Manipulation problem has been studied extensively in the literature for many voting rules. However, most studies have focused on the complete information setting, wherein the manipulators know the votes of the non-manipulators. While this assumption is reasonable for purposes of showing intractability, it is unrealistic for algorithmic considerations. In most real-world scenarios, it is impractical to assume that the manipulators to have accurate knowledge of all the other votes. In this work, we investigate manipulation with incomplete information. In our framework, the manipulators know a partial order for each voter that is consistent with the true preference of that voter. In this setting, we formulate three natural computational notions of manipulation, namely weak, opportunistic, and strong manipulation. We say that an extension of a partial order is viable if there exists a manipulative vote for that extension. We propose the following notions of manipulation when manipulators have incomplete information about the votes of other voters.
1. Weak Manipulation: the manipulators seek to vote in a way that makes their preferred candidate win in at least one extension of the partial votes of the non-manipulators.
2. Opportunistic Manipulation: the manipulators seek to vote in a way that makes their preferred candidate win in every viable extension of the partial votes of the non-manipulators.
3. Strong Manipulation: the manipulators seek to vote in a way that makes their preferred candidate win in every extension of the partial votes of the non-manipulators.
We consider several scenarios for which the traditional manipulation problems are easy (for instance, Borda with a single manipulator). For many of them, the corresponding manipulative questions that we propose turn out to be computationally intractable. Our hardness results often hold even when very little information is missing, or in other words, even when the instances are very close to the complete information setting. Our results show that the impact of paucity of information on the computational complexity of manipulation crucially depends on the notion of manipulation under consideration. Our overall conclusion is that computational hardness continues to be a valid obstruction to manipulation, in the context of a more realistic model.
2018-03-01T00:00:00Z