Worst-Case and Average-Case Hardness of Hypercycle and Database Problems

Cheng-Hao Fu, Andrea Lincoln, Rene Reyes · 2025

Read Worst-Case and Average-Case Hardness of Hypercycle and Database Problems by Cheng-Hao Fu, Andrea Lincoln, Rene Reyes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18640.txt.

Introduction

Cheng-Hao Fu, Andrea Lincoln, and Rene Reyes pin down the difficulty of cycle problems in hypergraphs and databases in a 2025 theoretical computer science study. Finding a minimum hypercycle, a closed loop in a generalized graph whose edges can hold many vertices, is a core primitive behind database query analysis. The authors prove lower bounds on running time that are tight, meaning no essentially faster algorithm exists under the usual assumptions.

A substantial regime of the unweighted problem gets the same tight treatment, while longer cycles admit a genuinely faster algorithm. A reduction also moves hardness from worst-case inputs to average ones for subgraph detection.

Catalog record

CREATORCheng-Hao Fu, Andrea Lincoln, Rene Reyes
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18640

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems Cheng-Hao Fu, Andrea Lincoln, Rene Reyes Abstract In this paper we present tight lower-bounds and new upper-bounds for hypergraph and database problems. We give tight lower-bounds for finding minimum hypercycles. We give tight lower-bounds for a substantial regime of unweighted hypercycle. We also give a new faster algorithm for longer unweighted hypercycles. We give a worst-case to average-case reduction from detecting a subgraph of a hypergraph in the worst-case to counting subgraphs of hypergraphs in the average-case. We demonstrate two applications of this worst-case to average-case reduction, which result in average-case lower bounds for counting hypercycles in random hypergraphs and queries in average-case databases. Our tight upper and lower bounds for hypercycle detection in the worst-case have immediate implications for the average-case via our worst-case to average-case reductions. 1 Introduction The fine-grained hardness of hypergraph problems is known to have interesting connections to both theoretical and practical problems in computer science. For example, hypergraph problems have deep connections to solving constraint satisfaction problems: algorithms for hypercycle problems in hypergraphs can be used to solve various Constraint Satisfaction Problems (CSPs), including Max- k -SAT [ LWW18 ] . On the practical side, a recent line of work in database theory (initiated by Carmeli and Kröll [ CK21 ] ) has shown that certain queries of interest can be interpreted as problems about detecting, listing and counting small structures in hypergraphs. Nevertheless, the fine-grained study of hypergraph problems remains largely under-explored, especially when compared to the volume of work on fine-grained hardness of graph problems. In this paper, we aim to extend the understanding of hypergraphs in the average-case setting. We focus on two main directions: the worst-case hardness of hypercycle problems and the average-case hardness of counting small subhypergraphs. To our knowledge, this work is the first to show that the conditional hardness of hypercycle detection is dependent on both the length of the hypercycle and the size of the hyperedges. This is somewhat surprising, given that for other problems, such as hyperclique detection, hardness is conjectured to depend only on the size of the hyperclique. In the weighted case we get tight lower bounds for all hypercycle lengths. In the unweighted case, we show that brute-force is necessary for short hypercycles, resulting in tight upper and lower bounds. For the parameter regime where we can’t show the brute force lower bound, we give a new faster algorithm for longer unweighted hypercycles using matrix multiplication. This shows the brute-force lower bound is actually false past the point where our reduction stops working. For our average-case results, we build on a line of work that has used the error-correcting properties of polynomials to show average-case fine-grained hardness. This technique, introduced by Ball et al. [ BRSV17 ] has already been applied to hypergraph problems by Boix-Adserà et al. [ BBB19 ] , who show that counting small hypercliques in random hypergraphs where all hyperedges have the same size is as hard as in the worst-case. In the graph setting, their approach was generalized by Dalirroyfard et al. [ DLW20 ] who showed similar worst-case-to-average-case reductions for counting any small subgraph. We further generalize their result to show that this is true for counting small subhypergraphs in random hypergraphs, including ones where the hyperedges have different sizes. The worst-case to average-case reduction also allows us to prove that counting queries on random databases are hard on average. These two results are highly complementary. Applying our worst-case-to-average-case reduction to our hypercycle hardness results immediately gives us average-case hardness of hypercycle problems. Furthermore, understanding the worst-case hardness of other hypergraph substructures would shed light on what types of counting queries are hard on average. Finally, in the process of exploring these areas, we have found many new avenues to explore, which range from understanding the parameter regimes where we do not get tight upper and lower bounds to improving some generic techniques from traditional worst-case reductions. 1.1 Hypercycle Algorithms and Lower Bounds A k -hypercycle in a u -uniform hypergraph is a list of k distinct nodes v_{1},\ldots,v_{k} such that every hyperedge of u adjacent nodes exists in the hypergraph. That is, a k -hypercycle consists of the edges (v_{i},\ldots,v_{i+u-1\mod k}) for all i\in[k] . In the literature, this is often called a tight hypercycle, but we will omit the ‘tight’ and call these hypercycles throughout this paper (following the norm of [ LWW18 ] ). We demonstrate new algorithms and conditional lower bounds for the minimum hypercycle and unweighted hypercycle problems. Our upper and lower bounds for minimum hypercycle are tight, as shown in Figure 1 . In the unweighted case, we show that the hardness of hypercycle detection depends on the relationship between the hyperedge size and hypercycle length, as shown in Figure 2 . The conditional lower bounds are derived from the minimum k -clique hypothesis and the (k,u) -hyperclique hypothesis: Definition 1. MIN WEIGHT k-CLIQUE HYPOTHESIS (e.g. [ AWW14 , BT17 ] ) There is a constant c>1 such that, on a Word-RAM with O(\log(n)) -bit words, finding a k -Clique of minimum total edge weight in an n -node graph with non-negative integer edge weights in [1,n^{ck}] requires n^{k-o(1)} time. Definition 2. (k,u) -HYPERCLIQUE HYPOTHESIS [ LWW18 ] Let k>u>2 be integers. On a Word-RAM with O(\log(n)) bit words, finding a k -hyperclique in a u -uniform hypergraph on n nodes requires n^{k-o(1)} time. As evidence for this hypothesis, [ LWW18 ] give a reduction from the maximum degree- u -CSP problem to the (k,u) -hyperclique problem. They also give a reduction from hyperclique detection to hypercycle detection. The hard instances output by this reduction only cover a specific hypercycle length k for each uniformity u and this seems inherent to the technique. A natural question to ask is whether the hardness of finding k -hypercycles in u -uniform hypergraphs depends on the relationship between u and k . We answer this question in the affirmative for both weighted and unweighted hypercycle problems. This is surprising since the hardness of other hypergraph problems such as (k,u) -hyperclique is conjectured to be independent of this relationship. For min-weight k -hypercycle, we show that brute-force is required when k is less than 2u-1 . When k\geq 2u-1 , we give an algorithm with runtime independent of k . For unweighted hypercycle, we show that brute force is needed for all k up to the length of the instances output by the [ LWW18 ] reduction. For longer hypercycles, we show this is not the case by giving novel algorithms which use matrix multiplication to get a speedup. We now provide a more detailed overview of our techniques along with formal theorem statements for our upper and lower bounds. 1.1.1 Weighted Hypercycle In Section 5 we give the results for weighted hypercycle, depicted in Figure 1 . The matching lower bounds come from a reduction between cliques in graphs (2-uniform hypergraphs) and hypercycles. Informally the minimum k -clique hypothesis states that finding a minimum k -clique in a graph can’t be done faster than the naive algorithm which takes n^{k-o(1)} time (see definition 1.1 ). We prove the following. Theorem 1.1 . If the

Read the complete text