Zbigniew Lonc ; Paweł Naroski ; Paweł Rzążewski - Tight Euler tours in uniform hypergraphs - computational aspects

dmtcs:3755 - Discrete Mathematics & Theoretical Computer Science, September 26, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-2
Tight Euler tours in uniform hypergraphs - computational aspectsArticle

Authors: Zbigniew Lonc ORCID; Paweł Naroski ; Paweł Rzążewski

    By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are pairwise different. A tight tour in $H$ is a tight Euler tour if it contains all edges of $H$. We prove that the problem of deciding if a given $3$-uniform hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph), unless the ETH fails. We also present an exact exponential algorithm for the problem, whose time complexity matches this lower bound, and the space complexity is polynomial. In fact, this algorithm solves a more general problem of computing the number of tight Euler tours in a given uniform hypergraph.

    Volume: Vol. 19 no. 3
    Section: Analysis of Algorithms
    Published on: September 26, 2017
    Accepted on: August 11, 2017
    Submitted on: July 2, 2017
    Keywords: Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 868 times.
    This article's PDF has been downloaded 347 times.