| 1. |
- Björklund, Andreas
(författare)
-
Determinant sums for undirected Hamiltonicity
- 2010
-
Ingår i: 2010 IEEE 51st Annual Symposium On Foundations Of Computer Science. - 0272-5428. - 9780769542447 ; , s. 173-182
-
Konferensbidrag (refereegranskat)abstract
- Abstract in UndeterminedWe present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running in O*(1.657(n)) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the O*(2(n)) bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems.For bipartite graphs, we improve the bound to O*(1.414(n)) time. Both the bipartite and the general algorithm can be implemented to use space polynomial in n.We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for k-Path (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers (Bjorklund STACS 2010) to evaluate it.
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
The Parity of Directed Hamiltonian Cycles
- 2013
-
Ingår i: Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 727-735
-
Konferensbidrag (refereegranskat)abstract
- We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
|
|
| 3. |
- Isaksson, Marcus, 1978, et al.
(författare)
-
The geometry of manipulation - A quantitative proof of the gibbard satterthwaite theorem
- 2010
-
Ingår i: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010; Las Vegas, NV; 23 October 2010 through 26 October 2010. - 0272-5428. - 9780769542447 ; :Article number 5671191, s. 319-328
-
Konferensbidrag (refereegranskat)abstract
- We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of q >= 4 alternatives and n voters will be manipulable with probability at least 10(-4)epsilon(2)n(-3)q(-30), where epsilon is the minimal statistical distance between f and the family of dictator functions. Our results extend those of [1], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [2], [3], [4], [5], [6]) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.
|
|
