Access the full text.
Sign up today, get DeepDyve free for 14 days.
Abasi et al. (2014) introduced the following two problems. In the r-Simple k-Path problem, given a digraph G on n vertices and positive 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 succinctly encodes some polynomial P on n variables and positive integers k, r, decide whether P has a monomial of total degree k where the degree of each variable is at most r. Abasi et al. obtained randomized algorithms of running time 4(k/r)log r nO(1) for both problems. Gabizon et al. (2015) designed deterministic 2O((k/r)log r) nO(1)-time algorithms for both problems (however, for the (r, k)-Monomial Detection problem the input circuit is restricted to be non-canceling). Gabizon et al. also studied the following problem. In the P-Set (r, q)-Packing Problem, given a universe V, positive integers (p, q, r), and a collection H of sets of size P whose elements belong to V, decide whether there exists a subcollection H of H of size q where each element occurs in at most r sets of H. Gabizon et al. obtained a deterministic 2O((pq/r)log r) nO(1)-time algorithm for P-Set (r, q)-Packing. The above results prove that the three problems are single-exponentially fixed-parameter tractable (FPT) parameterized by the product of two parameters, that is, k/r and log r, where k=pq for P-Set (r, q)-Packing. Abasi et al. and Gabizon et al. asked whether the log r factor in the exponent can be avoided. Bonamy et al. (2017) answered the question for (r, k)-Monomial Detection by proving that unless the Exponential Time Hypothesis (ETH) fails there is no 2o((k/r) log r) (n + log k)O(1)-time algorithm for (r, k)-Monomial Detection, i.e., (r, k)-Monomial Detection is unlikely to be single-exponentially FPT when parameterized by k/r alone. The question remains open for r-Simple k-Path and P-Set (r, q)-Packing. We consider the question from a wider perspective: are the above problems FPT when parameterized by k/r only, i.e., whether there exists a computable function f such that the problems admit a f(k/r)(n+log k)O(1)-time algorithm? Since r can be substantially larger than the input size, the algorithms of Abasi et al. and Gabizon et al. do not even show that any of these three problems is in XP parameterized by k/r alone. We resolve the wider question by (a) obtaining a 2O((k/r)2 log(k/r)) (n + log k)O(1)-time algorithm for r-Simple k-Path on digraphs and a 2O(k/r) &sdot (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 (in contrast, we prove that P-Multiset (r, q)-Packing is W[1]-hard), and (c) proving that (r, k)-Monomial Detection is para-NP-hard even if only two distinct variables are in polynomial P and the circuit is non-canceling. For the special case of (r, k)-Monomial Detection where k is polynomially bounded by the input size (which is in XP), we show W[1]-hardness. Along the way to solve 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. All our algorithms are deterministic.
ACM Transactions on Algorithms (TALG) – Association for Computing Machinery
Published: Jan 21, 2021
Keywords: (r, k)-monomial detection
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.