PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams

arXiv:1712.08147v4cs.DS

TL;DR

For sparse graphs, dense-case equivalences do not appear to hold, and the introduction notes no convincing reduction establishing Shortest Cycle hardness from the listed prior hardness sources. The paper reduces minimum-weight clique to sparse cycles and combines this with reductions to other graph problems. For the listed weighted-graph problems, the stated result concludes that the Min Weight (2ℓ+1)-Clique Hypothesis is false.

  • Problem

    For sparse graphs, dense-case equivalences do not appear to hold, and the introduction notes no convincing reduction establishing Shortest Cycle hardness from the listed prior hardness sources.

    Source: §1 · p. 2

  • Method

    The paper reduces minimum-weight clique to sparse cycles and combines this with reductions to other graph problems.

    Source: §1 · pp. 2–3

  • Results

    For the listed weighted-graph problems, the stated result concludes that the Min Weight (2ℓ+1)-Clique Hypothesis is false.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results provide conditional evidence that near-mn running times are optimal for the listed problems on an infinite family of edge sparsities.

    Source: §1 · pp. 2–3

    The authors note that the Yuster–Zwick running time for k-cycle might not be optimal.

    Source: §1 · p. 4

Abstract

from arXiv · show

Fine-grained reductions have established equivalences between many core problems with $\tilde{O}(n^3)$-time algorithms on $n$-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have $\tilde{O}(mn)$-time algorithms on $m$-edge $n$-node weighted graphs, and such algorithms have wider applicability. Are these $mn$ bounds optimal when $m \ll n^2$? Starting from the hypothesis that the minimum weight $(2\ell+1)$-Clique problem in edge weighted graphs requires $n^{2\ell+1-o(1)}$ time, we prove that for all sparsities of the form $m = \Theta(n^{1+1/\ell})$, there is no $O(n^2 + mn^{1-\epsilon})$ time algorithm for $\epsilon>0$ for \emph{any} of the below problems: Minimum Weight $(2\ell+1)$-Cycle in a directed weighted graph, Shortest Cycle in a directed weighted graph, APSP in a directed or undirected weighted graph, Radius (or Eccentricities) in a directed or undirected weighted graph, Wiener index of a directed or undirected weighted graph, Replacement Paths in a directed weighted graph, Second Shortest Path in a directed weighted graph, Betweenness Centrality of a given node in a directed weighted graph. That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems including $k$-cycle, shortest cycle, Radius, Wiener index and APSP.

1 Introduction

The introduction asks whether sparse weighted graph problems can beat known near-mn running times despite dense-graph equivalences. It answers conditionally by connecting minimum-weight clique hardness to sparse cycle hardness and extending the consequences to other graph problems.

1 Introduction

  • Earlier sparsity-preserving reductions transfer Shortest Cycle hardness to APSP and several related directed-graph problems, but gave no compelling reason Shortest Cycle itself needs mn time.The paper uses the clique-to-cycle connection to address this gap.Source: §1 · p. 2
  • The central technical contribution connects dense small-clique complexity to small-cycle complexity in sparse graphs.The paper also reduces Minimum Weight (2ℓ+1)-Clique to Minimum Weight (2ℓ+1)-Cycle on a directed sparse graph.Source: §1 · pp. 2–3
  • For m = Θ(n^(1+1/ℓ)), an O(n^2 + mn^(1−ε)) algorithm for any of eight weighted graph problems would refute the Min Weight (2ℓ+1)-Clique Hypothesis.The problems include Minimum Weight (2ℓ+1)-Cycle, Shortest Cycle, APSP, Radius, Wiener index, Replacement Paths, Second Shortest Path, and Betweenness Centrality.Source: §1 · p. 3
  • The weighted results also rule out runtimes of the form ˜O(m^(1+ε)n^(1−2ε)) for Shortest Cycle, assuming Min Weight Clique hardness.The introduction derives this consequence by applying its lower bounds at m = Θ(n^(1+1/L)).Source: §1 · p. 3
  • The weighted k-cycle conditional lower bounds are tight up to polylogarithmic overhead, matching the unweighted cycle algorithms’ exponents for odd and even k.The cited exponents are 2−2/(k+1) for odd k and 2−2/k for even k.Source: §1 · p. 3
  • Under the k-Clique Hypothesis, unweighted Shortest Cycle requires m^(2ω/3−o(1)) time, with the same lower bound extending to APSP, Radius, Betweenness Centrality, and Wiener Index.The reduction from k-clique to k-cycle also works on unweighted graphs by disregarding weights.Source: §1 · p. 3
  • Under the (ℓ,k)-Hyperclique Hypothesis, directed unweighted Shortest Cycle requires m^(k/(k−1)−o(1)) time, with examples yielding m^(3/2−o(1)) and m^(4/3−o(1)) bounds.The latter example is conditional on Exact Weight k-Clique lacking a significantly faster-than-n^k algorithm.Source: §1 · p. 5
  • For intermediate densities, the paper gives improved but non-matching lower bounds between the stated sparsity families.The reductions and matching weighted cycle algorithms are outlined as the paper’s core technical sequence.Source: §1 · p. 5

2 Preliminaries

The preliminaries establish the graph conventions, hardness hypotheses, and cycle-reduction tools used in the paper. They also define the layered structures that make the reductions easier to state.

Definitions and notation

  • Graphs are directed unless stated otherwise; k and ℓ are constants, and hypergraphs use m for hyperedges and n for vertices.A k-uniform hypergraph has hyperedges of size k; an ℓ-hyperclique has every k-vertex subset as a hyperedge, while a simple ℓ-hypercycle uses distinct vertices and consecutive k-tuples as hyperedges.Source: §2 · p. 5

Simple k-Cycle Reductions

  • A k-circle-layered graph partitions vertices into k groups, with edges only from each group to the next cyclically; k-cycle and k-clique hardness can be considered in these structured graphs.For odd k, the paper also uses a reduction from k-cycle to (k+1)-cycle.Source: §2 · pp. 5–6

Hardness hypotheses

  • The Min Weight k-Clique Hypothesis requires n^(k−o(1)) time on a Word-RAM for k-cliques of minimum total weight with integer edge weights bounded by n^ck.The weights are nonnegative and lie in [1,n^ck], for a constant c>1.Source: §2 · pp. 5–6
  • Exact Weight k-Clique asks for a k-clique with total edge weight zero; it is at least as hard as Min Weight k-Clique, and its hardness implies the k=3 hypothesis is especially plausible.The stated hypothesis requires n^(k−o(1)) time for integer weights in [−n^ck,n^ck].Source: §2 · p. 6
  • The Max-k-SAT Hypothesis posits a 2^(n−o(n))-time requirement, and its failure would also undermine the stated hyperclique hypothesis.The paper notes that hyperclique hypotheses connect to harder constraint-satisfaction problems, while the hypergraphs considered are dense and sparser ones can admit faster solutions.Source: §2 · p. 6

Simple k-Cycle Reductions

  • A k-cycle of weight Y can be converted in linear time to a (k+1)-cycle of the same weight using at most 2n vertices and n+m edges.The construction splits vertices in one layer and adds a zero-weight edge; its corollary transfers layered cycle detection algorithms with runtime O(m+n)+T(2n,m+n).Source: §2 · pp. 6–7
  • Detecting cycles in a general directed graph can be reduced to detection in a circle-layered graph with a stated ˜O(k^k(m+n+T(m,n))) runtime.Table 2 summarizes unweighted graph lower bounds; bold marks the paper’s results, and an asterisk marks conjectured upper bounds.Source: Table 2 · p. 6, §2 · p. 7
  • Random color-coding retains edges that advance one color cyclically, producing a k-circle-layered subgraph while preserving a given k-cycle with probability at least 1/k^k.Repeating O(k^k log n) times finds such a cycle with high probability.Source: §2 · p. 7

3 Reduction from Hyperclique to Hypercycle

The reduction converts an ℓ-partite k-uniform hypergraph into a γ-uniform hypergraph, where γ = ℓ−⌈ℓ/k⌉+1, so ℓ-hypercliques correspond to ℓ-hypercycles. It also preserves minimum weights, transferring the weighted problem.

3 Reduction from Hyperclique to Hypercycle

  • Color coding reduces the hyperclique search to 2^O(k) log n k-partite instances, with the randomized construction derandomizable by standard techniques.A fixed k-clique has all vertices colored differently with probability 1/(2e)^k.Source: §3 · p. 7
  • The construction takes O(n^γ) time and creates a γ-uniform hypergraph whose ℓ-hypercycles correspond exactly to ℓ-hypercliques with one vertex from each part.A candidate hyperedge is added when every size-k subset of its vertices is an edge in the original graph.Source: §3 · pp. 7–8
  • The construction can preserve minimum weight: a minimum-weight ℓ-hypercycle corresponds to a minimum-weight ℓ-hyperclique.Original hyperedge weights are assigned to responsible hyperedges so that each represented clique’s total weight is preserved.Source: §3 · pp. 7–8
  • γ = ℓ−⌈ℓ/k⌉+1 consecutive parts suffice because every choice of k vertices is contained in such a set.The arc argument bounds the smallest covering set by ℓ−⌈ℓ/k⌉+1.Source: §3 · p. 7

4 Reduction from Hypercycle to Cycle in Directed Graphs

A k-hypercycle in a λ-uniform hypergraph can be represented by a directed k-cycle in a graph with nearly the same number of nodes as the hypergraph’s λ-th power. The construction preserves minimum weight, and yields sparse-graph cycle lower bounds.

4 Reduction from Hypercycle to Cycle in Directed Graphs

  • A λ-uniform hypergraph on n nodes can be converted in ˜O(n^λ) time to a directed graph with O(n^{λ−1}) nodes and O(n^λ) edges, preserving k-hypercycle existence and minimum weight.If k is odd, the graph can be made undirected.Source: §4 · p. 8
  • For general ℓ and k, the reduction gives a minimum-weight ℓ-cycle lower bound of Ω(m^{ℓ/λ−o(1)}) at m = Θ(n^{1+1/(λ−1)}), where λ = ℓ−⌈ℓ/k⌉+1.The reduction produces (n_old)^λ edges from an instance requiring (n_old)^ℓ time.Source: §4 · p. 9
  • The Min Weight k-Clique Hypothesis also implies a minimum-weight k-cycle lower bound of O(nm^{⌈k/2⌉/λ−ε}) at m = Θ(n^{1+1/(λ−1)}), with λ = k−⌈k/2⌉+1.For odd k, the cycle result also holds in undirected graphs.Source: §4 · p. 9
  • Under the Min Weight (2k + 1)-Clique Hypothesis, minimum-weight (2k + 1)-cycle requires ruling out O(mn^{1−ε}) time for every ε > 0 when m = Θ(n^{1+1/k}).The result holds for directed and undirected graphs.Source: §4 · p. 9
  • Under the Exact Weight (2k + 1)-Clique Hypothesis, exact-weight (2k + 1)-cycle cannot be solved in O(mn^{1−ε}) time for m = Θ(n^{1+1/k}).The result applies to directed and undirected graphs.Source: §4 · p. 9

5 Probably Optimal Weighted k-Cycle Algorithms

The section gives matching conditional lower bounds and algorithms for minimum-weight ℓ-cycle on m-edge graphs. The algorithm adapts the Alon–Yuster–Zwick approach to weighted cycles, with a separate shortest-cycle-through-a-source procedure.

5 Probably Optimal Weighted k-Cycle Algorithms

  • Minimum Weight ℓ-Cycle requires m^{2−2/ℓ−o(1)} time for even ℓ and m^{2−2/(ℓ+1)−o(1)} time for odd ℓ, assuming the Min Weight ℓ-Clique Hypothesis.The odd-ℓ bound follows from a reduction producing O(n^{(ℓ+1)/2}) edges; the even-ℓ bound uses Lemma 2.1.Source: §5 · p. 9
  • Minimum Weight ℓ-Cycle can be solved in ˜O(m^{2−2/ℓ}) time for even ℓ and ˜O(m^{2−2/(ℓ+1)}) time for odd ℓ.The algorithm adapts Alon, Yuster and Zwick’s unweighted method by checking high-degree vertices, then enumerating and matching shorter paths in the remaining graph.Source: §5 · pp. 9–10
  • A weighted shortest ℓ-cycle through a source can be found in ˜O(m) time per color-coding trial by restricting paths to successive colors, running Dijkstra’s algorithm, and closing the cycle.The randomized procedure is repeated O(ℓ^ℓ log n) times; perfect hash families derandomize it.Source: §5 · p. 10
  • For low-degree cycles, the algorithm minimizes the combined weight of two oppositely directed paths and retains the ˜O(m^{2−1/⌈ℓ/2⌉}) runtime.The path sets are sorted by endpoints and weight.Source: §5 · p. 10

6 Hardness Results for Shortest Cycle

The section reduces minimum-weight k-cycle to shortest cycle and derives sparse-graph hardness for shortest-cycle problems. It also gives conditional lower bounds for unweighted directed shortest cycle from several hypotheses.

6 Hardness Results for Shortest Cycle

  • If Shortest Cycle can be solved in T(N,M) time, then Minimum Weight k-cycle can be solved in ˜O(T(n,m)) time.For unweighted k-cycle, the analogous reduction makes any k-cycle the shortest cycle in the constructed directed circle-layered graph.Source: §6 · p. 10
  • If Min Weight (2L + 1)-Clique requires n^{2L+1−o(1)} time, directed weighted Shortest Cycle requires mn^{1−o(1)} time when m = Θ(n^{1+1/L}).The reduction from minimum-weight k-cycle to Shortest Cycle uses a weight shift so that longer cycles cannot be shortest.Source: §6 · p. 10
  • Directed unweighted Shortest Cycle requires m^{3/2−o(1)} time under the Max 3 SAT Hypothesis, m^{4/3−o(1)} under the Exact Weight K Clique Hypothesis, and m^{2ω/3−o(1)} under the K-Clique Hypothesis.The Max 3 SAT argument selects ℓ divisible by 3 and greater than 3/ε to obtain a faster ℓ-cycle algorithm if the stated Shortest Cycle bound fails.Source: §6 · p. 10
  • A similar argument shows that m^(4/3−o(1)) time is needed under the Exact Weight K Clique Hypothesis, while m^(2ω/3−o(1)) time is needed under the K-Clique Hypothesis.Source: §6 · p. 10

7 Discussion of the Hyperclique Hypothesis

The paper argues that the dense (ℓ,k)-Hyperclique hypothesis is plausible because faster algorithms for k>2 have resisted substantial effort and connect to hard SAT and clique problems. Its scope is dense hypergraphs; faster algorithms are known for sparse instances.

7 Discussion of the Hyperclique Hypothesis

  • For k>2, the fastest known ℓ-hyperclique algorithms take n^ℓ−o(1) time despite attempts to adapt matrix-multiplication techniques.The paper points to its Section 8 result on tensor rank and border rank as ruling out that arithmetic-circuit approach.Source: §7 · p. 11
  • Williams reduced Max-3-SAT to 4-Hyperclique, so an O(n^4−ε)-time algorithm would yield a faster-than-brute-force Max-3-SAT algorithm.The paper generalizes this connection to Max-k-SAT and ℓ-hyperclique, and notes that related CSPs are included.Source: §7 · p. 11
  • The Exact Weight k-Clique conjecture is implied by Min Weight k-Clique, and for k=3 it connects to both APSP and 3SUM hardness.The cited reductions show that a truly subcubic Exact Weight 3-Clique algorithm would refute both conjectures.Source: §7 · p. 11
  • The hypothesis concerns dense hypergraphs; sparse ℓ-hyperclique instances have faster algorithms, with a cited bound of m^ℓ−1/2^Θ(√log m).This bound is attributed to results of Gao et al..Source: §7 · p. 11

8 No Generalized Matrix Multiplication for k>2

The section asks whether generalized tensor matrix multiplication can provide a faster route to hyperclique detection. It reduces hyperclique detection to this product, then shows that arithmetic circuits cannot improve on the trivial bound for k>2.

8 No Generalized Matrix Multiplication for k>2

  • The section builds the k+1-hyperclique reduction by grouping vertices into c-tuples and making hyperedges when the required k-subsets are present.The construction has O(n^c) nodes and takes O(n^ck) time; the paper extends the reduction from k+1 to ℓ-hyperclique.Source: §8 · p. 11
  • A k-wise product of k copies of a hypergraph's adjacency tensor detects a (k+1)-hyperclique when its output is nonzero on a hyperedge.Thus an algorithm for the product would give an algorithm for this hyperclique detection task.Source: §8 · p. 12
  • The paper rules out an arithmetic-circuit improvement for generalized matrix multiplication when k>2.It frames this as excluding an analogue of fast clique algorithms for hyperclique, not all possible algorithmic approaches.Source: §8 · p. 12
  • Theorem 8.1 states that for every k≥3, the border rank of the k-wise matrix multiplication tensor is exactly n^k+1.The proof sketch uses a flattening whose rank supplies a lower bound on the tensor's border rank.Source: §8 · p. 12
  • The border-rank result leaves open faster algorithms using operations beyond +,·,/; the paper mentions bit-level methods as one possibility.The stated exclusion is specifically for the arithmetic-circuit approach.Source: §8 · p. 12

9 Max-k-SAT to Tight Hypercycle

The section reduces Max-3-SAT to tight hypercycle and directed cycle problems to derive conditional running-time lower bounds. It also reviews prior exact algorithms for the graph problems covered by the paper.

9 Max-k-SAT to Tight Hypercycle

  • The reduction chain maps Max-3-SAT instances through tight hypercycle detection to directed L-cycle instances, with the corollary specifying graph size and edge count.The graph has N=2n^(d−1)/L nodes and M=2n^d/L edges, where d=L−⌈L/3⌉+1.Source: §9 · p. 13
  • For L > 3, solving directed L-cycle in O(M^(cL−ε)), where cL = L/(L−⌈L/3⌉+1), yields Max-3-SAT in Õ(2^((1−ε′)n)), which remains exponential.For large constant L, the theorem gives a lower bound of approximately M^(3/2) for detecting L-cycles.Source: §9 · p. 13
  • For directed 7-cycle on graphs with M=N^5/4, an O(M^7/5−ε)-time algorithm would imply a subexponential-time algorithm for Max-3-SAT.The paper contrasts its 7/5 exponent with the earlier 4/3 bound for many small cycle lengths.Source: §9 · p. 13

A Prior Work On Improved Running Times

  • Prior work gives exact algorithms with different bounds across directed and undirected cycle, APSP, and radius problems.The cited work includes O(mn) shortest cycle and sparse APSP algorithms, while other bounds depend on weight ranges or graph direction.Source: A Prior Work On Improved Running Times · p. 16
  • Prior exact algorithms for replacement paths and second shortest paths include an Õ(m) undirected bound and O(mn+n^2 loglog n) for directed arbitrary-weight graphs.For Wiener index, the cited best algorithms compute APSP and sum pairwise distances; Brandes' betweenness algorithm is also described.Source: A Prior Work On Improved Running Times · p. 16

B.1 Undirected k-cycle reduces to radius

The section reduces directed k-cycle problems to radius computation on undirected graphs. Its weighted construction encodes cycle weights in distances, while a separate unweighted reduction distinguishes whether a k-cycle exists by the radius threshold.

B.1 Undirected k-cycle reduces to radius

  • An undirected weighted Radius algorithm with running time f(N,M) yields a minimum-weight directed k-cycle algorithm in Õ(f(O(n),O(m)) log R + m) time.The input cycle weights are in [−R,R].Source: §B.1 · p. 17
  • The weighted reduction makes a shortest path encode the weight of a k-cycle through a corresponding node, allowing radius to test for a negative cycle.The section first reduces minimum k-cycle to negative k-cycle in a k-circle-layered graph, using logarithmically many threshold queries.Source: §B.1 · pp. 16–17
  • If a negative k-cycle exists, the constructed graph has radius below kF; the highlighted result states that the key path then has length less than kF.The radius threshold distinguishes the negative-cycle case in the weighted gadget.Source: §B.1 · p. 17
  • For undirected unweighted graphs, an O(f(O(n),O(m))+m)-time Radius algorithm detects directed k-cycles via a reduction with roughly the same number of nodes.The constructed radius is k if a k-cycle exists and larger otherwise.Source: §B.1 · p. 17
  • The unweighted test returns true exactly when the constructed graph's radius is k or less.This provides a direct radius-based decision procedure for k-cycle existence.Source: §B.1 · p. 18

B.2 Undirected k-cycle reduces to Wiener index

This section reduces minimum-weight k-cycle detection to Wiener index computation in undirected graphs, including unweighted graphs. The reductions encode cycle existence in distances between designated vertex sets and recover their distance sums from Wiener indices.

B.2 Undirected k-cycle reduces to Wiener index

  • A Wiener index algorithm on an undirected weighted graph yields a solution to minimum-weight k-cycle, with a threshold distinguishing whether a negative k-cycle exists.The reduction subtracts other distance contributions; the adjusted cross-part sum is compared with (kF − kR)|V1|^2 + |V1|kR.Source: §B.2 · pp. 18–20
  • To recover the designated cross-part distance sum, the weighted reduction subtracts Wiener indices of induced subgraphs and separately accounts for auxiliary-node distances.It also computes distances involving B and the auxiliary pair; the total reduction time is O(f(N,M + N)+M lg(N)).Source: §B.2 · pp. 19–20
  • An undirected unweighted Wiener index algorithm solves directed k-cycle in near-linear reduction overhead.The constructed graph has a lower Wiener index when a k-cycle exists and a larger one otherwise.Source: §B.2 · p. 20
  • The unweighted gadget encodes cycle existence through distances between V1 and V′1: a k-cycle gives a shorter corresponding path than its absence.The reduction tests whether the recovered cross-part distance sum is below |V1|^2k + |V1|.Source: §B.2 · p. 20
  • At density M = ˜Θ(N^1+1/L), a fast Wiener index algorithm implies a fast minimum-weight k-cycle algorithm for weighted and unweighted cases.The corollary applies to undirected Wiener index computation.Source: §B.2 · p. 20

B.3 Undirected k-cycle reduces to APSP

The section connects undirected APSP and Radius to minimum-weight k-cycle hardness, and then introduces reductions between hyperclique and degree-k-CSP problems. It also states that breaking the hyperclique hypothesis would yield faster algorithms for degree-k-CSP variants.

B.3 Undirected k-cycle reduces to APSP

  • A reduction from directed minimum-weight k-cycle to undirected Radius, followed by APSP-to-Radius computation, transfers the same lower bounds to undirected APSP.The authors note that reducing directed Shortest Cycle to undirected APSP is more problematic; their reduction also works for unweighted graphs.Source: §B.3 · p. 21
  • An O(n^2 + mn^1−ε)-time APSP algorithm would give an O(n^2 + mn^1−ε)-time Radius algorithm across directed or undirected, weighted or unweighted graphs..Source: §B.3 · p. 21

C General CSP to Hyperclique

  • The general CSP-to-hyperclique section defines maximum and weighted degree-k-CSP variants, then reduces these problems to hyperclique finding.The paper states that breaking the (ℓ,k)-hyperclique hypothesis yields 2^(1−ε)n-time algorithms for these CSP variants for some ε > 0.Source: C General CSP to Hyperclique · p. 21

C.1 Degree-k-CSP to Weighted Hyperclique

This section encodes degree-k-CSP assignments as weighted hypercliques, with hyperclique weights representing clause-polynomial values and assignment values. The resulting reductions use maximum-weight or exact-weight hyperclique algorithms to solve the corresponding CSP variants.

C.1 Degree-k-CSP to Weighted Hyperclique

  • Boolean degree-g polynomial coefficients are bounded by [−2^g−1, 2^g−1] for g > 0, and the proof extends Williams’s argument by induction.The induction splits a polynomial according to the final Boolean variable and bounds the resulting coefficient difference.Source: §C.1 · p. 21
  • A degree-k-CSP instance becomes a k-uniform hypergraph on ℓ2^n/ℓ nodes, where each ℓ-hyperclique represents an assignment.Its W1 edge weights sum to the clause-polynomial objective, while W2 weights sum to assignment bits; the encoding runs in O(mnk2^k2^n/ℓ) time for constant ℓ and k.Source: §C.1 · pp. 21–22
  • The encoding assigns every monomial and variable contribution exactly once across the hyperclique’s edge weights.W1 carries the sum of clause polynomials and W2 carries the sum of assignment bits.Source: §C.1 · p. 22
  • A maximum-weight ℓ-hyperclique algorithm solves maximum degree-k-CSP, with running time O(T(ℓ2^n/ℓ) + mnkℓ2^kn/ℓ) for constant ℓ and k.The maximizing hyperclique corresponds to the assignment maximizing the sum of clause-polynomial values.Source: §C.1 · p. 22
  • An exact-weight ℓ-hyperclique algorithm likewise solves weighted degree-k-CSP, using edge weights that combine the clause and assignment totals.The construction searches for a target weight encoding both sums.Source: §C.1 · p. 22

C.2 Degree-k-CSP to Unweighted Hyperclique

This section removes hyperclique edge weights by guessing their values and deleting edges that do not match each guess. The resulting reductions connect unweighted hyperclique algorithms to maximum and weighted degree-k-CSP, with consequences under the hyperclique hypothesis.

C.2 Degree-k-CSP to Unweighted Hyperclique

  • The section notes that Max-ℓ-SAT is a special case of maximum degree-ℓ-CSP, while no 2^(1−ε)n algorithm for Max-3-SAT is known.The paper presents this as motivation for reducing CSP variants to unweighted hyperclique.Source: §C.2 · pp. 22–23
  • An unweighted ℓ-hyperclique algorithm yields algorithms for maximum degree-k-CSP and weighted degree-k-CSP through multiple instances.The reductions enumerate possible edge-weight assignments and retain hypercliques matching the target weights.Source: §C.2 · p. 23
  • The unweighted reductions guess hyperclique edge weights, discard edges inconsistent with each guess, and run unweighted hyperclique instances.The authors note this introduces a large polynomial overhead.Source: §C.2 · pp. 22–23
  • An algorithm breaking the (ℓ,k)-hyperclique hypothesis runs in n^ℓ−ε time for some ε > 0.For constant ℓ and k, this yields 2^(1−ε/ℓ−o(1))n-time algorithms for maximum and weighted degree-k-CSP.Source: §C.2 · p. 23

D Bounds for Graph Densities for NonInteger L

Appendix D tightens conditional lower bounds between the densities where the paper establishes tight mn hardness, improving on the staircase bound. It also gives a color-coding self-reduction that relates k-cycle instances at different densities.

D Bounds for Graph Densities for NonInteger L

  • At m = n^(1+1/L), the lower bound is tight up to no(1) factors against the O~(mn) upper bound; between these points it forms a staircase.The staircase lower bound is n^(2+1/(L+1)) between the specified sparsity points.Source: D Bounds for Graph Densities for… · p. 23
  • The self-reduction uses random vertex coloring to create smaller, sparser instances, then checks color assignments to find k-cycles.Color classes have size about n/c; the approach considers c^k colorings and does not work for L = 1 because color-coding a dense graph leaves many dense graphs.Source: D Bounds for Graph Densities for… · p. 24
  • The reduction removes high-degree vertices and overloaded color classes before searching the remaining graph for minimum k-cycles.The proof bounds the high-degree search by nm/g and the overloaded-set removal by O(nm log(n)/c).Source: D Bounds for Graph Densities for… · p. 24
  • Lemma D.2 assumes odd k-clique hardness for k > 5 and gives an improved bound for c = n^δ in the stated δ range.The improvement is over the bound from (k+1)-clique.Source: D Bounds for Graph Densities for… · p. 24
  • For odd k, k-cycle is mn-hard at m = n^((k+1)/(k−1)), and (k+2)-cycle is m'n-hard at m = n^((k+3)/(k+1)).These are the two density endpoints spanned by the parameter range described for k > 5.Source: D Bounds for Graph Densities for… · p. 24
  • The improved intermediate-density lower bound beats the staircase when δ < 4/((k−1)(k^2−k+4)).The paper says this bound rules out the staircase as the true difficulty between the density points.Source: D Bounds for Graph Densities for… · pp. 24–25
Loading 1712.08147v4…