Pith. sign in

REVIEW 2 major objections 6 minor 33 references

On the Complexity of Problems on Graphs Defined on Groups

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Under ETH, invariant problems are never NP-complete on power graphs, yet Graph Motif defeats quasipolynomial time.

desk verdict 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. read the letter →

arxiv 2507.05860 v1 pith:TMFAV7V7 submitted 2025-07-08 cs.CC cs.DMmath.GR

Bireswar Das , Dipan Dey , Jinia Ghosh This is my paper · ORCID
classification cs.CCcs.DMmath.GR MSC 68Q1768Q2505C2520D60
keywords complexitytheorypowergraphsdefinedongroupsexponentialtimehypothesisgraphmotifproblemisomorphism-invariantproblemsweightedmax-cutrecognition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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)}$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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).

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 (2)
  1. [§4, Theorem 17 (p. 11–12)] 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.
  2. [§5, Lemma 21 (p. 13–14)] 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.
minor comments (6)
  1. [§3, proof of Theorem 4] 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).
  2. [§5, p. 13, reduced graph definition] 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)'.
  3. [§5, Lemma 21 proof, p. 14] 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.
  4. [§4, Corollary 16, p. 11] The displayed running time '2nc/ log logn' is ambiguous; it should read 2^{n^{c/\log\log n}}.
  5. [§2, p. 4] The Euler totient formula for ϕ(p1^{α1}...pk^{αk}) is missing a product symbol; as printed it reads as a single term.
  6. [§4, Lemma 13, p. 8] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main hardness results are explicit reductions, and the recognition algorithms reuse a published prior-work subroutine as an external black box rather than as a self-defined conclusion.

full rationale

The derivation chain for the main lower bounds is self-contained. Theorem 4 is a direct application of Babai canonization plus the standard fact that quasipolynomially sparse languages are not NP-complete under ETH; it does not assume the non-NP-completeness it concludes. Lemma 13 is an explicit many-one reduction from 3-SAT to Graph Motif on Pow(Z_N), with correctness shown by the divisibility characterization (Remark 1) and by explicit inequalities (C(2k,k) >= 2n and the phi-product bound); the target hardness is not fed in as an input. Weighted Max-Cut hardness is an explicit embedding of K_n into the generator clique of Pow(Z_{n^2}). The Section 5 recognition algorithms do import the p-group directed-power-graph isomorphism test from the authors' earlier FSTTCS paper [10]; this is self-citation, but [10] is a published parameter-free algorithm with stated assumptions, and the present paper supplies the independent reduction/gluing and enumeration steps, so the citation does not make the argument circular. The manuscript itself flags in Appendix A.2 that [10] is a promise algorithm that can false-positive, which is a correctness caveat, not a self-referential step. Theorem 9's proof is only sketched as 'similar,' an omission but not a circular reduction. The only in-scope concern I would record separately is Theorem 17: the greedy test uses set inclusion 'If M is a subset of {col(v)} ∪ col(N_C(v))' although M is defined as a multiset, so the proof as written can accept colour-multiset violations; this is a correctness gap, not a circular derivation, and it does not affect Theorem 12 or the other hardness results.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper is conditional-complexity work; its free parameters are zero. It relies on standard tools (ETH, Babai canonization, Mahaney-style sparsity, group enumeration, Ganian's algorithm) and on the authors' earlier power-graph isomorphism algorithm [10]. The only ad hoc premise is the set-only motif check in the p-group algorithm, which is flagged in red flags.

assumptions (8)
  • domain assumption Exponential Time Hypothesis: 3-SAT cannot be solved in 2^{o(n)} time.
    Used explicitly in Theorems 4, 5, 9 and 12; all non-hardness and lower-bound statements are conditional on it.
  • standard math Babai's quasipolynomial-time graph canonization and graph isomorphism algorithm [5].
    Foundation of the sparse-set argument in Theorem 4; treated as a black box.
  • standard math Mahaney-type sparse-set theorem: under ETH no quasipolynomially sparse language is NP-complete.
    Used to conclude non-NP-completeness of the canonicalized language L'.
  • standard math Quasipolynomial upper bound 2^{O(log^3 n)} on the number of non-isomorphic groups of order n [27].
    Bounding the number of canonical power graphs; also referenced in Remark 6.
  • standard math Ganian's FPT algorithm for Graph Motif parameterized by neighbourhood diversity [17].
    Used for the subexponential algorithm on power graphs of cyclic groups in Corollary 16.
  • standard math Structure facts about power graphs: complete iff cyclic prime-power order [9], automorphism formula for Pow(Z_n) [14], and the order-divisibility characterization for cyclic groups.
    Used in Lemma 8, Lemma 3, and throughout the p-group and cyclic-group arguments.
  • standard math Prior isomorphism algorithm for directed power graphs of p-groups and nilpotent groups by Das, Ghosh and Kumar [10], including the reduced-graph characterization and p-group linear-time isomorphism.
    Provides the subroutine behind the recognition algorithms in Section 5.
  • ad hoc to paper A motif occurrence in a p-group power graph component can be certified by checking whether the motif's colour set is contained in the closed neighbourhood of a dominating vertex.
    Theorem 17's algorithm checks set containment and its correctness proof swaps one vertex of matching colour. This is valid only for colourful motifs, while M was defined as a multiset, so the general statement relies on an unsupported premise.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Problems on Graphs Defined on Groups." pith.science (2026). https://pith.science/paper/TMFAV7V7

@misc{pith2026250705860,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Problems on Graphs Defined on Groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TMFAV7V7}},
  note         = {Machine review of arXiv:2507.05860}
}
read the original abstract

We study the complexity of graph problems on graphs defined on groups, especially power graphs. We observe that an isomorphism invariant problem, such as Hamiltonian Path, Partition into Cliques, Feedback Vertex Set, Subgraph Isomorphism, cannot be NP-complete for power graphs, commuting graphs, enhanced power graphs, directed power graphs, and bounded-degree Cayley graphs, assuming the Exponential Time Hypothesis (ETH). An analogous result holds for isomorphism invariant group problems: no such problem can be NP-complete unless ETH is false. We show that the Weighted Max-Cut problem is NP-complete in power graphs. We also show that, unless ETH is false, the Graph Motif problem cannot be solved in quasipolynomial time on power graphs, even for power graphs of cyclic groups. We study the recognition problem of power graphs when the adjacency matrix or list is given as input and show that for abelian groups and some classes of nilpotent groups, it is solvable in polynomial time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages

  1. [1]

    On the Structure of the Power Graph and the Enhanced Power Graph of a Group

    G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish and F. Shaveisi. “On the Structure of the Power Graph and the Enhanced Power Graph of a Group”. In: The Electronic Journal of Combinatorics (2017), P3–16

    work page 2017

  2. [2]

    T. M. Apostol. Introduction to analytic number theory . Springer Science & Business Media, 2013

    work page 2013

  3. [3]

    Aspects of the commuting graph

    V. Arvind, X. Ma, P. J. Cameron and N. V. Maslova. “Aspects of the commuting graph”. In: arXiv preprint arXiv:2305.07301 (2023)

    work page Pith review arXiv 2023

  4. [4]

    Solvable group isomorphism is (almost) in NP /spl cap/ CoNP

    V. Arvind and J. Toran. “Solvable group isomorphism is (almost) in NP /spl cap/ CoNP”. In: Proceedings. 19th IEEE Annual Conference on Computational Complexity,

    work page

  5. [5]

    Graph isomorphism in quasipolynomial time

    L. Babai. “Graph isomorphism in quasipolynomial time”. In: Proceedings of the forty- eighth annual ACM symposium on Theory of Computing. 2016, pp. 684–697

    work page 2016

  6. [6]

    The graph motif problem parameterized by the structure of the input graph

    É. Bonnet and F. Sikora. “The graph motif problem parameterized by the structure of the input graph”. In: Discrete Applied Mathematics 231 (2017), pp. 78–94

    work page 2017

  7. [7]

    Superpolynomial circuits, almost sparse oracles and the exponential hierarchy

    H. Buhrman and S. Homer. “Superpolynomial circuits, almost sparse oracles and the exponential hierarchy”. In: Foundations of Software Technology and Theoretical Com- puter Science. Ed. by R. Shyamasundar. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 116–127. ISBN : 978-3-540-47507-1

    work page 1992

  8. [8]

    Graphs defined on groups

    P. J. Cameron. “Graphs defined on groups”. In: International Journal of Group Theory 11.2 (2022), pp. 53–107. 18 REFERENCES

    work page 2022

Show all 33 references
  1. [9]

    Undirected power graphs of semigroups

    I. Chakrabarty, S. Ghosh and M. Sen. “Undirected power graphs of semigroups”. In: Semigroup Forum. Vol. 78. Springer. 2009, pp. 410–426

    2009

  2. [10]

    The Isomorphism Problem of Power Graphs and a Question of Cameron

    B. Das, J. Ghosh and A. Kumar. “The Isomorphism Problem of Power Graphs and a Question of Cameron”. In: 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Vol. 323. LIPIcs. 2024, 20:1–20:23

    2024

  3. [11]

    The minimal faithful permutation degree of groups without abelian normal subgroups

    B. Das and D. Thakkar. “The minimal faithful permutation degree of groups without abelian normal subgroups”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024, pp. 118–129

    2024

  4. [12]

    Succinct representation of finite abelian groups

    A. Farzan and J. I. Munro. “Succinct representation of finite abelian groups”. In: Proceedings of the 2006 international symposium on Symbolic and algebraic computation. 2006, pp. 87–92

    2006

  5. [13]

    Sharp tractability borderlines for finding connected motifs in vertex-colored graphs

    M. R. Fellows, G. Fertin, D. Hermelin and S. Vialette. “Sharp tractability borderlines for finding connected motifs in vertex-colored graphs”. In: International Colloquium on Automata, Languages, and Programming. Springer. 2007, pp. 340–351

    2007

  6. [14]

    The full automorphism group of the power (di)graph of a finite group

    M. Feng, X. Ma and K. Wang. “The full automorphism group of the power (di)graph of a finite group”. In: European Journal of Combinatorics 52 (2016), pp. 197–206. ISSN : 0195-6698

    2016

  7. [15]

    S. R. Finch. Mathematical constants. Cambridge university press, 2003

    2003

  8. [16]

    The polycyclic length of linear and finite polycyclic groups

    R. Fisher. “The polycyclic length of linear and finite polycyclic groups”. In: Canadian Journal of Mathematics 26.4 (1974), pp. 1002–1009

    1974

  9. [17]

    Using neighborhood diversity to solve hard problems

    R. Ganian. “Using neighborhood diversity to solve hard problems”. In: arXiv preprint arXiv:1201.3091 (2012)

    2012 arXiv

  10. [18]

    NP-hard sets are not sparse unless P= NP: An exposition of a simple proof of Mahaney’s Theorem, with applications

    J. A. Grochow. “NP-hard sets are not sparse unless P= NP: An exposition of a simple proof of Mahaney’s Theorem, with applications”. In: arXiv preprint arXiv:1610.05825 (2016)

    2016 arXiv

  11. [19]

    Geometric algorithms and combinatorial optimization

    M. Grötschel, L. Lovasz and A. Schrijver. “Geometric algorithms and combinatorial optimization”. In: Algorithms and Combinatorics 2 (1988)

    1988

  12. [20]

    Finding and counting vertex-colored subtrees

    S. Guillemot and F. Sikora. “Finding and counting vertex-colored subtrees”. In: Al- gorithmica 65 (2013), pp. 828–844

    2013

  13. [21]

    Enumerating p-groups. I: Inequalities

    G. Higman. “Enumerating p-groups. I: Inequalities”. In: Proceedings of the London Mathematical Society 3.1 (1960), pp. 24–30

    1960

  14. [22]

    Which problems have strongly exponential complexity?

    R. Impagliazzo, R. Paturi and F. Zane. “Which problems have strongly exponential complexity?” In: Journal of Computer and System Sciences 63.4 (2001), pp. 512–530

    2001

  15. [23]

    A combinatorial property and power graphs of groups

    A. V. Kelarev and S. J. Quinn. “A combinatorial property and power graphs of groups”. In: Contributions to general algebra 12.58 (2000), pp. 3–6

    2000

  16. [24]

    Motif search in graphs: application to metabolic networks

    V. Lacroix, C. G. Fernandes and M. -F. Sagot. “Motif search in graphs: application to metabolic networks”. In: IEEE/ACM transactions on computational biology and bioinformatics 3.4 (2006), pp. 360–368

    2006

  17. [25]

    Algorithmic meta-theorems for restrictions of treewidth

    M. Lampis. “Algorithmic meta-theorems for restrictions of treewidth”. In: Algorithmica 64 (2012), pp. 19–37

    2012

  18. [26]

    Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

    S. R. Mahaney. “Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis”. In: Journal of Computer and System Sciences 25.2 (1982), pp. 130–143

    1982

  19. [27]

    Enumerating finite groups

    A. McIver and P. M. Neumann. “Enumerating finite groups”. In: The Quarterly Journal of Mathematics 38.4 (1987), pp. 473–488

    1987

  20. [28]

    On the nlog n isomorphism technique (a preliminary report)

    G. L. Miller. “On the nlog n isomorphism technique (a preliminary report)”. In: Proceedings of the tenth annual ACM symposium on theory of computing. 1978, pp. 51– 58. Appendix 19

    1978

  21. [29]

    Deterministic parameterized algorithms for the graph motif problem

    R. Y. Pinter, H. Shachnai and M. Zehavi. “Deterministic parameterized algorithms for the graph motif problem”. In: Discrete Applied Mathematics 213 (2016), pp. 162–178

    2016

  22. [30]

    The undirected power graph of a finite group

    G. Pourgholi, H. Yousefi-Azari and A. Ashrafi. “The undirected power graph of a finite group”. In: Bulletin of the Malaysian Mathematical Sciences Society 38.4 (2015), pp. 1517–1525

    2015

  23. [31]

    Ribenboim

    P. Ribenboim. The new book of prime number records . Springer Science & Business Media, 2012

    2012

  24. [32]

    Approximate formulas for some functions of prime numbers

    J. B. Rosser and L. Schoenfeld. “Approximate formulas for some functions of prime numbers”. In: Illinois Journal of Mathematics 6.1 (1962), pp. 64–94

    1962

  25. [33]

    J. J. Rotman. An introduction to the theory of groups . Springer Science & Business Media, 2012. A Appendix A.1 Proof of Claim 1 of Lemma 13 Suppose that Φ has a satisfying assignment, in which each clause Cj, 1 ⩽ j ⩽ m, of Φ has at least one true literal. We select the vertic...

    2012

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.