## Abstract

We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2^{n}? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0 < λ < 1 and prime p we can count the Hamiltonian cycles modulo p^{[(1-λ) n/3p]} in expected time less than cn for a constant c < 2 that depends only on p and λ. Such an algorithm was previously known only for the case of counting modulo two [Björklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in O∗(3^{n-α}(G)) time and polynomial space, where α(G) is the size of the maximum independent set in G. In particular, this yields an O∗(3^{n/2}) time algorithm for bipartite directed graphs, which is faster than the exponential-space algorithm in [Cygan et al., STOC 2013]. Our algorithms are based on the algebraic combinatorics of "incidence assignments" that we can capture through evaluation of determinants of Laplacian-like matrices, inspired by the Matrix-Tree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the Matrix-Tree Theorem to derive simple algebraic algorithms for detecting out-branchings. Specifically, we give an O∗(2κ)-time randomized algorithm for detecting out-branchings with at least k internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Björklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial detection problem.

Original language | English (US) |
---|---|

Title of host publication | 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 |

Editors | Anca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770415 |

DOIs | |

State | Published - Jul 1 2017 |

Externally published | Yes |

Event | 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland Duration: Jul 10 2017 → Jul 14 2017 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 80 |

ISSN (Print) | 1868-8969 |

### Other

Other | 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 |
---|---|

Country/Territory | Poland |

City | Warsaw |

Period | 7/10/17 → 7/14/17 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Counting
- Directed Hamiltonicity
- Graph Laplacian
- Independent set
- Kinternal out-branching