تقرير
Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
| العنوان: | Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree |
|---|---|
| المؤلفون: | Liu, Brian, Sheffield, Nathan S., Westover, Alek |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity |
| الوصف: | We study the following generalization of the Hamiltonian cycle problem: Given integers $a,b$ and graph $G$, does there exist a closed walk in $G$ that visits every vertex at least $a$ times and at most $b$ times? Equivalently, does there exist a connected $[2a,2b]$ factor of $2b \cdot G$ with all degrees even? This problem is NP-hard for any constants $1 \leq a \leq b$. However, the graphs produced by known reductions have maximum degree growing linearly in $b$. The case $a = b = 1 $ -- i.e. Hamiltonicity -- remains NP-hard even in $3$-regular graphs; a natural question is whether this is true for other $a$, $b$. In this work, we study which $a, b$ permit polynomial time algorithms and which lead to NP-hardness in graphs with constrained degrees. We give tight characterizations for regular graphs and graphs of bounded max-degree, both directed and undirected. Comment: 16 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.16270 |
| رقم الأكسشن: | edsarx.2405.16270 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |