2018/06/24 by Gregory Gutin, Gutin, Gregory, Magnus Wahlström +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1806.09108
openalex publication_date 2018/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abasi et al. (2014) and Gabizon et al. (2015) studied the following problems. In the r-Simple k-Path problem, given a digraph G on n vertices and integers r,k, decide whether G has an r-simple k-path, which is a walk where every vertex occurs at most r times and the total number of vertex occurrences is k. In the (r,k)-Monomial Detection problem, given an arithmetic circuit that encodes some polynomial P on n variables and integers k,r, decide whether P has a monomial of degree k where the degree of each variable is at most~r. In the p-Set (r,q)-Packing problem, given a universe V, positive integers p,q,r, and a collection \cal H of sets of size p whose elements belong to V, decide whether there exists a subcollection \cal H' of \cal H of size q where each element occurs in at most r sets of \cal H'. Abasi et al. and Gabizon et al. proved that the three problems are single-exponentially fixed-parameter tractable (FPT) when parameterized by (k/r)log r, where k=pq for p-Set (r,q)-Packing and asked whether the log r factor in the exponent can be avoided. We consider their question from a wider perspective: are the above problems FPT when parameterized by k/r only? We resolve the wider question by (a) obtaining a 2O((k/r)2log(k/r)) (n+log k)O(1)-time algorithm for r-Simple k-Path on digraphs and a 2O(k/r) (n+log k)O(1)-time algorithm for r-Simple k-Path on undirected graphs (i.e., for undirected graphs we answer the original question in affirmative), (b) showing that p-Set (r,q)-Packing is FPT, and (c) proving that (r,k)-Monomial Detection is para-NP-hard. For p-Set (r,q)-Packing, we obtain a polynomial kernel for any fixed p, which resolves a question posed by Gabizon et al. regarding the existence of polynomial kernels for problems with relaxed disjointness constraints.