2014/01/22 by Ran Ben Basat, Ben-Basat, Ran, Ariel Gabizon +1
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Optimization and Search Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1401.5707
openalex publication_date 2014/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a directed graph on n vertices. Given an integer k<=n, the SIMPLE k-PATH problem asks whether there exists a simple k-path in G. In case G is weighted, the MIN-WT SIMPLE k-PATH problem asks for a simple k-path in G of minimal weight. The fastest currently known deterministic algorithm for MIN-WT SIMPLE k-PATH by Fomin, Lokshtanov and Saurabh runs in time O(2.851k⋅ nO(1)⋅ log W) for graphs with integer weights in the range [-W,W]. This is also the best currently known deterministic algorithm for SIMPLE k-PATH- where the running time is the same without the log W factor. We define Lk(n)⊆ [n]k to be the set of words of length k whose symbols are all distinct. We show that an explicit construction of a non-deterministic automaton (NFA) of size f(k)⋅ nO(1) for Lk(n) implies an algorithm of running time O(f(k)⋅ nO(1)⋅ log W) for MIN-WT SIMPLE k-PATH when the weights are non-negative or the constructed NFA is acyclic as a directed graph. We show that the algorithm of Kneis et al. and its derandomization by Chen et al. for SIMPLE k-PATH can be used to construct an acylic NFA for Lk(n) of size O^*(4k+o(k)). We show, on the other hand, that any NFA for Lk(n) must be size at least 2k. We thus propose closing this gap and determining the smallest NFA for Lk(n) as an interesting open problem that might lead to faster algorithms for MIN-WT SIMPLE k-PATH. We use a relation between SIMPLE k-PATH and non-deterministic xor automata (NXA) to give another direction for a deterministic algorithm with running time O^*(2k) for SIMPLE k-PATH.