On r-Simple k-Path

DOI10.1007/978-3-662-44465-8_1MaRDI QIDQ2922590zbMATH OpenOpenAlexFDO

Authors Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, Elad Haramaty

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.4863

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: An $r$-simple $k$-path is a {path} in the graph of length $k$ that passes through each vertex at most $r$ times. The $r$-SIMPLE $k$-PATH problem, given a graph $G$ as input, asks whether there exists an $r$-simple $k$-path in $G$. We first show that this problem is NP-Complete. We then show that there is a graph $G$ that contains an $r$-simple $k$-path and no simple path of length greater than $4logk/logr$. So this, in a sense, motivates this problem especially when one's goal is to find a short path that visits many vertices in the graph while bounding the number of visits at each vertex. We then give a randomized algorithm that runs in time ${\displaystyle }$mathrm{poly}(n)cdot 2^{O( kcdot log r/r)}${\displaystyle }$ that solves the $r$-SIMPLE $k$-PATH on a graph with $n$ vertices with one-sided error. We also show that a randomized algorithm with running time $mathrmpoly(n)cdot{2}^{(c/2)k/r}$ with $c<1$ gives a randomized algorithm with running time $poly(n)cdot{2}^{cn}$ for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an $O(logr)$ factor.

Recommendations

• On \(r\)-simple \(k\)-path and related problems parameterized by \(k/r\)
• r -Simple k -Path and Related Problems Parameterized by k / r
• On the Kőnig‐Egerváry theorem for ‐paths
• k-cuts on a path
• A note on the path graph P_k(G)
• On \(k\)-path pancyclic graphs
• k-paths of k-trees
• On the vertex \(k\)-path cover
• Near-shortest and K-shortest simple paths

Cited in

(10)

• Kernelization of cycle packing with relaxed disjointness constraints
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Detecting monomials with k distinct variables
• r -Simple k -Path and Related Problems Parameterized by k / r
• Tight lower bounds for the complexity of multicoloring
• On \(r\)-simple \(k\)-path and related problems parameterized by \(k/r\)
• Almost optimal cover-free families
• On the Kőnig‐Egerváry theorem for ‐paths
• A simple inclusion-exclusion based algorithm for (k, n)-MLC and related problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time

This page was built for publication: On r-Simple k-Path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922590)