{"id":"d5d57d35-62d7-46fa-bb79-89bcbf737638","arxiv_id":"2507.05860","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under ETH, isomorphism-invariant problems cannot be NP-complete on power graphs; Graph Motif is hard on power graphs of cyclic groups, and recognition is polynomial for abelian and some nilpotent power graphs.","lead":"Power graphs turn a finite group into a graph by connecting elements when one is a power of the other. This paper maps which graph problems stay hard on such graphs and which become easy or provably not NP-complete, under a standard complexity assumption.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 17's p-group Graph Motif algorithm checks the closed-neighbourhood colour set instead of the colour multiset, so it returns false positives when M has repeated colours; the polynomial-time upper bound is incomplete as written.","rationale":"I focused first on Theorem 12, the strongest hardness claim: the embedding in Lemma 13 is intricate, but the divisibility characterization, the binomial inequality for fP, the phi-product lower bound, and the edge/non-edge cases in Claim 2 all check out, including the potentially confusing point that fP ranges over indices {2,...,b} so the neighbour of r has odd order. I therefore found no reason to doubt the ETH-based super-quasipolynomial lower bound or the non-NP-completeness results for isomorphism-invariant problems. The genuine correctness problem is in Theorem 17: the algorithm's certificate is phrased as set inclusion although the motif is a multiset. The reader's weakest-assumption analysis already identified this, and my concrete counterexample confirms it lands. Because the fix is a simple multiset check that preserves the dominating-vertex argument, the correct evaluation is CONDITIONAL rather than REJECT: the main hardness landscape stands, but the stated polynomial-time algorithm for p-groups needs revision before the paper's full set of claims is sound. No further adjustment to the reader's verdict is needed.","tokens_in":22099,"tokens_out":28430,"duration_ms":327993,"concrete_test":"Run the Theorem 17 algorithm on Pow(Z_3 × Z_3) where all vertices except two generators a,b of one order-3 subgroup are coloured outside M, col(a)=R, col(b)=B, and M={R,R}. The surviving component is the connected edge {a,b}; at the dominating vertex a the set-inclusion check sees colour R and returns Yes, although no connected induced subgraph can contain two R vertices. A correct multiset-containment check must return No, demonstrating the bug.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main hardness results in Theorems 4 and 12 appear internally coherent, and I did not find a concrete flaw in the Lemma 13 embedding. The load-bearing gap is in the claimed polynomial-time upper bound, Theorem 17. The paper defines a motif as a multiset of colours, but the greedy algorithm tests the condition 'If M is a subset of {col(v)} ∪ col(N_C(v))' using set inclusion. Since the component C has a dominating vertex v, any occurrence can be rearranged to include v, so the correct certificate is multiset containment of M in the colour multiset of {v} ∪ N_C(v). Set containment is strictly weaker: it can be satisfied when M demands two vertices of one colour and only one such vertex exists. A concrete failure occurs on Pow(Z_3 × Z_3): keep only two generators a,b of one order-3 subgroup, colour a=R and b=B, and let M={R,R}. The remaining graph is the edge {a,b}, a is dominating, and set inclusion passes because the closed neighbourhood contains R; the algorithm would output Yes, but no connected subgraph has colour multiset {R,R}. The fix is to replace the set test with a multiset-counting test, after which the dominating-vertex argument goes through. This does not affect Theorem 12 or the ETH-based lower bound, but it does mean the paper's polynomial-time p-group claim is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of graph problems restricted to graphs defined on groups, with emphasis on power graphs. The main contributions are: (i) a proof that any isomorphism-invariant graph problem over power graphs, and also over commuting graphs, enhanced power graphs, directed power graphs, and bounded-degree Cayley graphs, cannot be NP-complete unless ETH fails, via canonization and sparsity (Theorem 4); an analogous statement for isomorphism-invariant group problems given by Cayley tables (Theorem 9); (ii) NP-completeness of Weighted Max-Cut on power graphs of cyclic groups (Theorem 11); (iii) an ETH-based lower bound showing Graph Motif on power graphs of cyclic groups cannot be solved in quasipolynomial time, proved by a reduction from 3-SAT using an embedding into Pow(Z_N) with N a product of the first O(log n) primes (Theorem 12 and Lemma 13); (iv) a claimed polynomial-time algorithm for Graph Motif on power graphs of p-groups (Theorem 17); and (v) polynomial-time recognition algorithms for power graphs of abelian groups, nilpotent groups of bounded polycyclic length, and nilpotent groups of squarefree exponent (Theorem 22 and Section 5).","tokens_in":22419,"tokens_out":31791,"duration_ms":349314,"significance":"If the main claims hold, the paper gives a fairly complete ETH-based picture for power graphs: invariant problems are not NP-complete, Weighted Max-Cut is NP-complete, Graph Motif requires super-quasipolynomial time even on cyclic power graphs, and recognition for abelian and some nilpotent classes is polynomial. The reduction in Lemma 13 is intricate and the divisibility argument is internally consistent; the use of Mahaney's theorem with Babai canonization is elegant. The paper also deserves credit for explicitly identifying (Appendix A.2) the false-positive problem in applying the earlier power-graph isomorphism algorithm of Das et al. to recognition. However, two load-bearing gaps remain: the p-group Graph Motif algorithm mishandles multiset motifs, and the reduction in Lemma 21 partitions by the prime factors of the wrong integer. Both are local and fixable, but they currently invalidate the statements of Theorem 17 and the proof of Theorem 22.","major_comments":[{"comment":"The algorithm tests the condition 'M is a subset of {col(v)} ∪ col(N_C(v))' using set inclusion, but M is defined as a multiset of colours (p. 7). This produces false positives when M has repeated colours. For example, in Pow(Z_3 × Z_3) take two elements a,b of order 3 that generate the same subgroup, colour a = R and b = B, and let M = {R,R}. After deleting vertices whose colours are not in M, the remaining graph is the single vertex a; a is dominating in its component and the closed-neighbourhood colour set is {R}, so the set-inclusion test passes and the algorithm answers Yes, although no connected induced subgraph has colour multiset {R,R}. The fix is to test multiset containment, counting multiplicities in the closed neighbourhood of a dominating vertex; with that replacement the dominating-vertex argument goes through. This gap does not affect Theorem 12, but it means the polynomial-time p-group claim is not established as written.","section":"§4, Theorem 17 (p. 11–12)"},{"comment":"The proof factors the number n of vertices of the input reduced directed graph and then partitions the graph into subgraphs induced by vertices whose out-degree is a power of one of the prime factors of n. The relevant primes, however, are the primes dividing the order of the group, and these need not divide n. A concrete counterexample is the reduced directed power graph of Z_3 × Z_3: it has 5 vertices (the identity class and four classes of order 3), so n = 5, but all out-degrees are 1 or 3; the algorithm would look for a subgraph on vertices with out-degree a power of 5, find none, and reject a valid abelian 3-group. The proof should instead compute the group order (or the set of primes appearing among the vertex colours) and partition by those primes. As written, this flaw undermines the proof of Lemma 21 and hence of Theorem 22, although it is local and fixable.","section":"§5, Lemma 21 (p. 13–14)"}],"minor_comments":[{"comment":"The proof concludes that L is not NP-hard under ETH from the quasipolynomial reducibility of L to the sparse language L'. Since Theorem 5 is stated for NP-completeness under polynomial-time reductions, please state explicitly the sparse-hardship variant for quasipolynomial reductions (or justify that the standard Mahaney argument adapts).","section":"§3, proof of Theorem 4"},{"comment":"In the bullet list defining the reduced graph, 'For each closed twin-class τ of R(D), we create a vertex in D' should read '... of D, we create a vertex in R(D)'.","section":"§5, p. 13, reduced graph definition"},{"comment":"The proof ends with an incomplete instruction: 'Then we run the Gluing process on inputs D; R(DPow(G); R(DPow(Gi)), Di, fi, for all 1 ≤ i ≤ k; .' Please complete the sentence and state explicitly that Anil returns Yes if and only if the Gluing process succeeds.","section":"§5, Lemma 21 proof, p. 14"},{"comment":"The displayed running time '2nc/ log logn' is ambiguous; it should read 2^{n^{c/\\log\\log n}}.","section":"§4, Corollary 16, p. 11"},{"comment":"The Euler totient formula for ϕ(p1^{α1}...pk^{αk}) is missing a product symbol; as printed it reads as a single term.","section":"§2, p. 4"},{"comment":"The notation P_{(b-1)/2}({2,3,...,b}) for subsets of indices is introduced abruptly; a sentence explaining that these are index subsets whose corresponding primes form the order of h would improve readability.","section":"§4, Lemma 13, p. 8"}],"recommendation":"major_revision","confidential_remarks":"The main ETH-based lower bounds (Theorems 4, 11, 12) appear sound and are the strongest part of the paper. The two gaps identified above are local and repairable; I do not see a reason to question the novelty or the authors' good faith. The paper is a preliminary FCT version; the Section 5 recognition part needs more careful rewriting, especially Lemma 21. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth knowing: Theorem 12 gives the first super-quasipolynomial lower bound for Graph Motif on cyclic power graphs under ETH, and the embedding (Lemma 13) is intricate but internally consistent. The divisibility argument works because fP uses prime indices, so the z-orders are odd and unwanted divisibility cannot occur. I checked the non-edge cases and they line up. The non-NP-completeness theorem (Theorem 4) is a clean application of quasipolynomial sparsity plus Babai canonization, not a deep result, but it is correct and worth stating. The recognition algorithms for abelian and bounded-polycyclic nilpotent groups are a solid contribution, building on the authors' earlier isomorphism work.\n\nThe soft spot is Theorem 17. The p-group algorithm tests whether the motif M is a subset of the colour set of a dominating vertex's closed neighbourhood. But M is defined as a multiset, and set inclusion is strictly weaker than multiset containment. A concrete false positive: take Pow(Z_3 × Z_3), keep two generators a,b of one order-3 subgroup, colour a=R and b=B, and let M={R,R}. The remaining graph is the edge ab; a dominates the component, its closed neighbourhood has colour set {R,B}, and set inclusion passes. But no connected subgraph has two R-vertices. The fix is to replace set inclusion with multiset-count containment; after that the dominating-vertex swap argument goes through and the algorithm is poly-time. As written, though, the polynomial-time claim for p-groups is not established. This does not affect Theorem 12 or the ETH-based lower bound.\n\nMinor: the Weighted Max-Cut result is what the authors say it is, unsurprising. The paper is honest about that.\n\nBottom line: the core hardness results are credible and the bug is isolated and easy to patch. This deserves a serious referee; I would send it to review with a request to fix Theorem 17. It will be useful to people in algebraic graph theory and ETH-based lower bounds. I would cite the Graph Motif result once the multiset issue is cleaned up.","headline":"The Graph Motif lower bound for cyclic power graphs is sound and new, but the p-group algorithm's set-vs-multiset bug makes Theorem 17 wrong as written.","tokens_in":22886,"tokens_out":3912,"would_cite":true,"duration_ms":40824,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","05C25","20D60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under ETH, invariant problems are never NP-complete on power graphs, yet Graph Motif defeats quasipolynomial time.","keywords":["complexity theory","power graphs","graphs defined on groups","exponential time hypothesis","graph motif problem","isomorphism-invariant problems","weighted max-cut","recognition problem"],"falsifier":"Compute, for increasing $n$ and $b = 2\\log(2n)+1$, the ratio $\\log \\phi(p_2\\cdots p_{(b+1)/2}) / \\log n$: the embedding requires it to stay above 3 (to absorb the $c n^3$ clause-neighbourhood bound) while $\\log N / \\log n$ remains $O(\\log\\log n)$; if the ratio ever falls to 3 or below, Lemma 13's construction fails. Alternatively, a quasipolynomial-time algorithm for Graph Motif on power graphs of cyclic groups would directly refute Theorem 12.","tokens_in":21914,"feed_emoji":"🧩","tokens_out":20200,"duration_ms":178455,"temperature":0.7,"pith_summary":"This paper maps the computational complexity of power graphs, the graphs whose vertices are elements of a group and whose edges join elements linked by a power relation. Its central claim is a sharp asymmetry under the Exponential Time Hypothesis: any problem whose answer is unchanged by renaming vertices—Hamiltonian Path, Partition into Cliques, Feedback Vertex Set, Subgraph Isomorphism, and similar—cannot be NP-complete on power graphs, commuting graphs, enhanced power graphs, directed power graphs, or bounded-degree Cayley graphs. The reason is that such problems reduce to quasipolynomially sparse languages via graph canonization, and sparse languages cannot be NP-complete under ETH. By contrast, label-sensitive problems are genuinely hard on power graphs: Weighted Max-Cut is NP-complete even for cyclic groups, and Graph Motif cannot be solved in quasipolynomial time even when the underlying group is cyclic. The same canonization argument also rules out NP-completeness for isomorphism-invariant group problems whose input is a Cayley table.","feed_headline":"Cyclic power graphs defeat quasipolynomial motif search","feed_subtitle":"ETH rules out fast motif algorithms even for cyclic groups; invariant problems are provably not NP-complete here.","key_machinery":"The central mechanism for the hardness results is the divisor-order characterization of cyclic power graphs: two elements of $\\mathbb{Z}_N$ are adjacent in $\\mathrm{Pow}(\\mathbb{Z}_N)$ exactly when one's order divides the other's. The 3-SAT-to-Graph-Motif reduction sets $N$ to the product of the first $b$ primes, with $b = 2\\log(2n)+1$, maps literals injectively to subsets of primes of size $(b-1)/2$ so that each literal's order is a distinct product $p_1$ times those primes, and places clause vertices in the equivalence class of the divisor element; the inequalities $\\binom{2k}{k} \\ge 2n$ and $c n^3 \\le \\phi(p_2\\cdots p_{(b+1)/2})$ guarantee the map is one-to-one and the neighbourhoods are large enough. For the non-hardness results, the carrying object is canonization: an isomorphism-invariant problem reduces to its canonical form, producing a language that is quasipolynomially sparse because the number of non-isomorphic groups of order $n$ is quasipolynomial. For the recognition algorithms, the machinery is the reduced directed power graph, the quotient by closed twin classes where each class consists of generators of the same cyclic subgroup, together with a gluing process that assembles colour-isomorphisms of Sylow $p$-subgroups into a colour-isomorphism of a nilpotent group.","core_discovery":"The paper proves, conditional on ETH, that the class of power graphs has a rigid complexity profile. Isomorphism-invariant graph problems over power graphs are never NP-complete, because quasipolynomial graph canonization, together with the quasipolynomial number of non-isomorphic groups of order $n$, turns any such problem into a quasipolynomially sparse language, which a classical sparse-set theorem forbids from being NP-complete under ETH. On the non-invariant side, Weighted Max-Cut is NP-complete for power graphs of cyclic groups by embedding a weighted complete graph into the clique of generators of $\\mathrm{Pow}(\\mathbb{Z}_{n^2})$. The main new hardness result is for Graph Motif: there is a reduction from 3-SAT that embeds any formula as an induced subgraph of $\\mathrm{Pow}(\\mathbb{Z}_N)$, where $N$ is the product of the first $O(\\log n)$ primes, yielding instances of size $N = 2^{O(\\log n \\log\\log n)}$; consequently no algorithm running in time $2^{O(\\log^c N)}$ for constant $c$ can solve Graph Motif on cyclic power graphs unless ETH fails. In the opposite direction, Graph Motif on power graphs of $p$-groups is solvable in polynomial time by a dominating-vertex greedy algorithm, and the recognition of power graphs of abelian groups, of nilpotent groups of bounded polycyclic length, and of nilpotent groups of squarefree exponent is polynomial-time.","pith_inferences":["The same canonization-plus-sparsity template would apply to any graph class with quasipolynomially many isomorphism types on $n$ vertices; power graphs are one instance, and the argument suggests a general criterion for when invariant problems evade NP-completeness under ETH.","The $2^{O(\\log n \\log\\log n)}$-size embedding indicates that the number of divisors of $N$, equivalently the neighbourhood diversity of $\\mathrm{Pow}(\\mathbb{Z}_N)$, is the parameter that really controls Graph Motif on cyclic power graphs: problems parameterized by neighbourhood diversity are FPT, while the ETH bound shows this parameter can be close to its maximum.","Because the $p$-group algorithm checks the colour set of a dominating vertex's closed neighbourhood, a natural verification is whether that certificate remains sufficient when the motif contains repeated colours, which the formal multiset definition of a motif allows.","The paper's own $\\mathrm{EXP} \\ne \\mathrm{NEXP}$ variants of the main theorems suggest the lower bound is not an artifact of ETH's particular formulation; a stronger testable version would ask whether the quasipolynomial barrier persists for any reduction whose image size is $n^{O(\\log\\log n)}$."],"forward_implications":["Under ETH, no isomorphism-invariant graph problem—Hamiltonian Path, Partition into Cliques, Feedback Vertex Set, Subgraph Isomorphism, graph colouring, and the like—is NP-complete on power graphs, commuting graphs, enhanced power graphs, directed power graphs, or bounded-degree Cayley graphs; the same holds for isomorphism-invariant group problems given by Cayley tables.","Weighted Max-Cut is NP-complete on power graphs even when the underlying group is cyclic, since the generator clique of $\\mathrm{Pow}(\\mathbb{Z}_{n^2})$ contains any weighted complete graph on $n$ vertices.","Graph Motif on power graphs of cyclic groups cannot be solved in time $2^{O(\\log^c n)}$ for any constant $c$ under ETH, and the same conclusion follows from the weaker assumption $\\mathrm{EXP} \\ne \\mathrm{NEXP}$.","Graph Motif on power graphs of cyclic groups is solvable in $2^{n^{O(1/\\log\\log n)}}$ time via neighbourhood diversity, so under ETH the problem sits strictly between quasipolynomial and subexponential time.","Graph Motif on power graphs of $p$-groups lies in P, and the recognition problem for power graphs of abelian groups, nilpotent groups of bounded polycyclic length, and nilpotent groups of squarefree exponent is solvable in polynomial time."],"supporting_citations":[{"why":"Quasipolynomial graph canonization, used in Theorem 4 to map invariant problem instances to canonical forms.","marker":"[5]"},{"why":"Sparse-set theorem stating that quasipolynomially sparse languages cannot be NP-complete under ETH, the basis of Theorem 5.","marker":"[26]"},{"why":"Quasipolynomial bound on the number of non-isomorphic groups of order n, which makes the canonical language sparse.","marker":"[27]"},{"why":"Definition of undirected power graphs and the lemma that the power graph is complete iff the group is cyclic of prime-power order, used for graph properties and the p-group algorithm.","marker":"[9]"},{"why":"FPT algorithm for Graph Motif parameterized by neighbourhood diversity, used for the subexponential upper bound on cyclic power graphs.","marker":"[17]"},{"why":"The Exponential Time Hypothesis itself, the assumption under which all conditional hardness and non-hardness statements are proved.","marker":"[22]"},{"why":"Reconstruction and isomorphism algorithms for power graphs, used in Section 5 for reduced directed power graphs and the linear-time p-group isomorphism.","marker":"[10]"},{"why":"Quasipolynomial recognition of commuting graphs via group descriptions, the template for the power-graph recognition framework.","marker":"[3]"},{"why":"Known connection between sparse languages and the exponential hierarchy, used in Remarks 10 and 14 for the EXP ≠ NEXP variants.","marker":"[7]"}],"fun_headline_variants":["ETH bars NP-completeness for invariant group graph problems","Cyclic power graphs foil quasipolynomial motif algorithms","Weighted Max-Cut is NP-complete on power graphs","Power graph recognition polynomial for abelian and nilpotent groups"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Graph Motif lower bound rests on the number-theoretic claim that a 3-SAT formula on $n$ variables embeds as an induced subgraph of $\\mathrm{Pow}(\\mathbb{Z}_N)$ with $N$ the product of the first $O(\\log n)$ primes: specifically, that at $b = 2\\log(2n)+1$ the inequalities $\\binom{2k}{k} \\ge 2n$ and $c n^3 \\le \\phi(p_2\\cdots p_{(b+1)/2})$ both hold for all large $n$, so the literal map is injective and the clause vertices have room to be placed.","fun_headline_variants_meta":{"raw":{"variants":["ETH bars NP-completeness for invariant group graph problems","Cyclic power graphs foil quasipolynomial motif algorithms","Weighted Max-Cut is NP-complete on power graphs","Power graph recognition polynomial for abelian and nilpotent groups"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000352,"raw_usage":{"total_tokens":1957,"prompt_tokens":1026,"completion_tokens":931,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":862}},"tokens_in":642,"tokens_out":931,"duration_ms":9362,"temperature":1.0,"reasoning_tokens":862,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:20:42.518011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for increasing $n$ and $b = 2\\log(2n)+1$, the ratio $\\log \\phi(p_2\\cdots p_{(b+1)/2}) / \\log n$: the embedding requires it to stay above 3 (to absorb the $c n^3$ clause-neighbourhood bound) while $\\log N / \\log n$ remains $O(\\log\\log n)$; if the ratio ever falls to 3 or below, Lemma 13's construction fails. Alternatively, a quasipolynomial-time algorithm for Graph Motif on power graphs of cyclic groups would directly refute Theorem 12.","supporting_citations":[{"cited_title":"Graph isomorphism in quasipolynomial time","cited_arxiv_id":null,"evidence_quote":"Quasipolynomial graph canonization, used in Theorem 4 to map invariant problem instances to canonical forms."},{"cited_title":"Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis","cited_arxiv_id":null,"evidence_quote":"Sparse-set theorem stating that quasipolynomially sparse languages cannot be NP-complete under ETH, the basis of Theorem 5."},{"cited_title":"Enumerating finite groups","cited_arxiv_id":null,"evidence_quote":"Quasipolynomial bound on the number of non-isomorphic groups of order n, which makes the canonical language sparse."},{"cited_title":"Undirected power graphs of semigroups","cited_arxiv_id":null,"evidence_quote":"Definition of undirected power graphs and the lemma that the power graph is complete iff the group is cyclic of prime-power order, used for graph properties and the p-group algorithm."},{"cited_title":"Which problems have strongly exponential complexity?","cited_arxiv_id":null,"evidence_quote":"The Exponential Time Hypothesis itself, the assumption under which all conditional hardness and non-hardness statements are proved."},{"cited_title":"The Isomorphism Problem of Power Graphs and a Question of Cameron","cited_arxiv_id":null,"evidence_quote":"Reconstruction and isomorphism algorithms for power graphs, used in Section 5 for reduced directed power graphs and the linear-time p-group isomorphism."},{"cited_title":"Aspects of the commuting graph","cited_arxiv_id":"2305.07301","evidence_quote":"Quasipolynomial recognition of commuting graphs via group descriptions, the template for the power-graph recognition framework."},{"cited_title":"Superpolynomial circuits, almost sparse oracles and the exponential hierarchy","cited_arxiv_id":null,"evidence_quote":"Known connection between sparse languages and the exponential hierarchy, used in Remarks 10 and 14 for the EXP ≠ NEXP variants."}],"review_version":1}