Tight Euler tours in uniform hypergraphs - computational aspects
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,...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3755/pdf |
| _version_ | 1797270078407835648 |
|---|---|
| author | Zbigniew Lonc Paweł Naroski Paweł Rzążewski |
| author_facet | Zbigniew Lonc Paweł Naroski Paweł Rzążewski |
| author_sort | Zbigniew Lonc |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:33Z |
| format | Article |
| id | doaj.art-6eeb6e9cc5f841fd8f665c9df8d595d8 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:33Z |
| publishDate | 2017-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-6eeb6e9cc5f841fd8f665c9df8d595d82024-03-07T15:34:15ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-09-01Vol. 19 no. 3Analysis of Algorithms10.23638/DMTCS-19-3-23755Tight Euler tours in uniform hypergraphs - computational aspectsZbigniew Lonchttps://orcid.org/0000-0001-6650-6774Paweł NaroskiPaweł RzążewskiBy 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.https://dmtcs.episciences.org/3755/pdfcomputer science - computational complexitycomputer science - data structures and algorithms |
| spellingShingle | Zbigniew Lonc Paweł Naroski Paweł Rzążewski Tight Euler tours in uniform hypergraphs - computational aspects Discrete Mathematics & Theoretical Computer Science computer science - computational complexity computer science - data structures and algorithms |
| title | Tight Euler tours in uniform hypergraphs - computational aspects |
| title_full | Tight Euler tours in uniform hypergraphs - computational aspects |
| title_fullStr | Tight Euler tours in uniform hypergraphs - computational aspects |
| title_full_unstemmed | Tight Euler tours in uniform hypergraphs - computational aspects |
| title_short | Tight Euler tours in uniform hypergraphs - computational aspects |
| title_sort | tight euler tours in uniform hypergraphs computational aspects |
| topic | computer science - computational complexity computer science - data structures and algorithms |
| url | https://dmtcs.episciences.org/3755/pdf |
| work_keys_str_mv | AT zbigniewlonc tighteulertoursinuniformhypergraphscomputationalaspects AT pawełnaroski tighteulertoursinuniformhypergraphscomputationalaspects AT pawełrzazewski tighteulertoursinuniformhypergraphscomputationalaspects |