Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard

Casper Gyurik; Massimiliano Incudini; Riccardo Molteni; Vedran Dunjko

REVIEW 3 major objections 4 minor 42 references

Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Testing balanced and bipartite components in sparse graphs is QMA1-hard.

desk verdict The paper's QMA1-hardness claims rest on a false unitary equivalence; the Hodge Laplacian diagonal does not match the signed graph degree, and the two-edge path is a counterexample. read the letter →

arxiv 2412.14932 v1 pith:DKILUKHV submitted 2024-12-19 quant-ph

Massimiliano Incudini , Casper Gyurik , Riccardo Molteni , Vedran Dunjko This is my paper · ORCID

classification quant-ph MSC 68Q1268Q1705C5055U10 PACS 03.67.Lx

keywords QMA1-hardnesssparsebalancednessbipartitednessCombinatorialHodgeLaplaciansignedgraphcliquehomologysignlessstoquasticHamiltonian

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

The paper sets out to prove that two basic structural tests on succinctly presented sparse graphs are quantumly hard: deciding whether a signed graph contains a balanced connected component, and deciding whether an unsigned graph contains a bipartite connected component. A balanced component is one whose vertices can be split into two groups so that edges inside a group are positive and edges between groups are negative; a bipartite component is one whose vertices split so that every edge crosses the split. The route is a chain of spectral equivalences: the $p$-th Combinatorial Hodge Laplacian of a simplicial complex is claimed to be unitarily equivalent to the signed Laplacian of a graph built from the $p$-simplices, so holes in a clique complex become balanced components of a signed graph, and a known negative-subdivision construction carries balanced components to bipartite components. Because clique homology is already known to be QMA1-hard, the paper concludes that sparse balancedness and sparse bipartitedness are QMA1-hard, with promise versions of both contained in QMA. A sympathetic reader cares because these are natural network-science properties, and the bipartite test adds an example where a spectral property of a stoquastic Hamiltonian is quantumly hard.

What carries the argument

The machine that carries the argument is the unitary equivalence $L_p^{\Gamma} \simeq L_{G_s}$ between the $p$-th Combinatorial Hodge Laplacian of a simplicial complex and the signed Laplacian of a graph $G_s$ on $p$-simplices. In matrix terms, the equivalence asserts that off-diagonal entries match products of face-orientation signs, with signs $s(\sigma,\tau)=-\bigl(\mathrm{sng}(\sigma\cap\tau,\sigma)\,\mathrm{sng}(\sigma\cap\tau,\tau)+\mathrm{sng}(\sigma,\sigma\cup\tau)\,\mathrm{sng}(\tau,\sigma\cup\tau)\bigr)$, and that diagonal entries equal degrees in the constructed graph. Around that identity sit two standard facts it mobilizes: $\ker L_p^{\Gamma}\cong H_p(\Gamma)$, so kernel non-triviality detects holes, and a signed graph has a balanced component exactly when its signed Laplacian has a zero eigenvalue. The second half of the proof machinery is the negative-subdivision construction, which replaces each positive edge by a two-edge path through a new vertex and turns balance into bipartiteness while keeping the graph sparse.

What would settle it

Compute the Combinatorial Hodge Laplacian at $p=1$ for the simplicial complex consisting of two edges sharing a vertex, and compare it with the signed Laplacian of the graph whose two vertices are those edges joined by the single edge between them: the former has diagonal entries $2$, the latter has diagonal entries $1$, so the claimed unitary equivalence fails on this instance unless signs or diagonal contributions are modified.

Watch

Extended reading notes

Core claim

The central discovery is a dictionary between simplicial complexes and signed graphs. The paper's Proposition 1 states that for any abstract simplicial complex $\Gamma$ and dimension $p$, the Combinatorial Hodge Laplacian $L_p^{\Gamma}$ is unitarily equivalent to the signed graph Laplacian $L_{G_s}$ of a graph whose vertices are the $p$-simplices of $\Gamma$; edges connect $p$-simplices that are either lower-adjacent (share a $(p-1)$-face) or upper-adjacent (lie in a common $(p+1)$-simplex), and the edge signs are products of oriented incidence signs. Since the kernel of $L_p^{\Gamma}$ is isomorphic to the $p$-homology of $\Gamma$, a non-trivial kernel in the clique complex is recast as a zero eigenvalue of a signed graph Laplacian, which is exactly the condition for a balanced connected component. The paper then applies the negative-subdivision operation, replacing positive edges by paths through new vertices, to convert balance into bipartiteness in an unsigned graph with comparable size and sparse access. The paper argues both steps can be implemented by polynomial-size classical circuits that provide sparse access in the marked (and, by an auxiliary construction, traditional) model, yielding the two QMA1-hardness theorems.

Load-bearing premise

The proof depends on the diagonal entries of the Hodge Laplacian matching the degrees of the vertices in the constructed signed graph; if a simplex's faces and cofaces do not produce exactly those neighbor counts, the equivalence breaks.

Editorial extensions

If this is right

Sparse balancedness and sparse bipartitedness are each QMA1-hard, so under the stated sparse-oracle input model both tasks are as hard as any problem admitting a perfect-completeness quantum witness.
The promise variants in which the smallest eigenvalue of the relevant Laplacian is either zero or at least inverse-polynomial are contained in QMA, placing them inside the quantum class rather than outside it.
Because the marked sparse-access model can be converted to the traditional sparse-access model for these problems, the hardness is not an artifact of the marked encoding.
Bipartite-component testing becomes another spectral property of a stoquastic Hamiltonian that is quantumly hard, complementing the known hardness of excited-state energies of stoquastic Hamiltonians.
The reduction transfers hardness from topological data analysis (clique homology) to network-science concepts (balance and bipartiteness), giving a complexity-theoretic bridge between the two areas.

Reading between the lines

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

The unitary equivalence, if it holds, would let spectral quantities of signed graphs (such as algebraic conflict measures) be transported to Combinatorial Hodge Laplacians and back, potentially giving new bounds on simplicial holes from signed-graph Cheeger inequalities; this direction is not explored in the paper.
The balance-to-bipartite half of the chain is independent of the Hodge-to-signed-graph step, so if the latter's diagonal-counting premise failed, a corrected diagonal (for example a weighted or looped graph variant) could still salvage the hardness conclusions through a different spectral characterisation.
A direct test of the equivalence on small complexes with known kernels, such as the boundary of a triangle at $p=1$ or a path of two edges, would separate a genuine spectral dictionary from a purely formal matrix similarity and is cheap to run.
These hardness results suggest that classical heuristics for balanced or bipartite component detection, which are polynomial-time on explicit graphs, must fail on succinctly specified sparse families unless the input is expanded to explicit form, an observation the paper leaves mostly implicit.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague, the short version: the paper advertises QMA1-hardness for testing balanced components in sparse signed graphs and bipartite components in sparse unsigned graphs, but the main reduction is built on Proposition 1, and Proposition 1 is false. The reader's counterexample is correct and lands directly: take the clique complex of the path on three vertices at p=1. The two edges form a complex with Hodge Laplacian [[2,-1],[-1,2]] (kernel trivial), while the Proposition 1 construction yields a single signed edge with graph Laplacian [[1,-1],[-1,1]] (kernel nontrivial). These are not unitarily equivalent, so the zero-eigenvalue correspondence collapses, and with it the completeness and soundness of Theorem 1. Theorem 2 inherits the failure.

The root issue is in the diagonal computation. The Hodge Laplacian's diagonal counts, for each p-simplex, its p+1 faces (always present) plus its cofaces. The graph Laplacian's diagonal counts distinct lower- and upper-adjacent p-simplices. Those are different: a face need not be contained in another p-simplex, and a coface contributes one graph neighbor, not deg^up. The proof around Equation 22 identifies the two without justification, and the example shows they genuinely differ.

What is good: the paper is clearly written, the sparse-access formalism is careful, and the containment-in-QMA arguments (Propositions 2 and 3) look plausible and self-contained. The Zaslavsky negative-subdivision reduction from balance to bipartiteness is a nice, correct observation, and the authors take care to preserve sparse access through it. The related-work discussion is honest and the open questions are sensible. If Proposition 1 could be repaired or replaced, the overall strategy might still work, but as it stands the hardness results are unsupported.

Who this is for: someone working on quantum Hamiltonian complexity might read the containment arguments or the Zaslavsky reduction, but the headline claims are not substantiated. It deserves a referee because the error is subtle and the intended result is significant, but a referee should be asked to focus on Proposition 1. My recommendation: do not accept as is; require repair of the reduction or an explicit statement of a restricted family where the equivalence holds.

Referee Report

3 major / 4 minor

Summary. The paper claims to prove QMA1-hardness of two graph problems: deciding whether a sparse signed graph has a balanced connected component (Theorem 1) and deciding whether a sparse unsigned graph has a bipartite connected component (Theorem 2). The proofs are built on Proposition 1, which asserts a unitary equivalence between the p-th Combinatorial Hodge Laplacian of an abstract simplicial complex and the signed Laplacian of a graph whose vertices are the p-simplices and whose edges correspond to lower and upper adjacency. The authors introduce a marked sparse-access model, give QMA containment arguments for promise variants via block encodings, and connect their results to hardness of spectral properties of stoquastic Hamiltonians.

Significance. If the main equivalence were correct, the paper would establish new QMA1-hardness results for natural network-science properties and would add another example of hard spectral questions for stoquastic Hamiltonians. The paper is clearly organized, and the treatment of sparse access and the QMA containment arguments are useful. However, the central unitary equivalence is false, so the two hardness theorems are not established; the proposed reduction fails on an elementary example within the intended reduction family.

major comments (3)

[Section III.C, Proposition 1 and Eqs. (19)-(23)] The claimed unitary equivalence is invalid because the diagonal entries of the two Laplacians do not match. In Eq. (20), the upper Laplacian diagonal is deg^up(sigma), the number of (p+1)-cofaces of sigma, while the degree of sigma in the upper-adjacency graph G^up_s counts upper-adjacent p-simplices, which equals (p+1) times the number of cofaces for p >= 1. Similarly, the lower Laplacian diagonal is p+1, but the degree in the lower-adjacency graph counts distinct p-simplices sharing a face with sigma, which need not equal p+1. A concrete counterexample from the reduction family is Gamma = Cl(P_3), the clique complex of the path on three vertices, at p=1. The two 1-simplices give L_1 = [[2,-1],[-1,2]] with trivial kernel, whereas the graph constructed in Proposition 1 is a single edge with signed Laplacian [[1,-1],[-1,1]] and nontrivial kernel. These matrices are not unitarily equivalent, so Proposition 1 is false.
[Section III.D, Theorem 1] Because Proposition 1 is the only bridge from clique homology to balanced components, the completeness and soundness steps of Theorem 1 collapse. The counterexample above is a no-instance of clique homology (trivial first homology) that maps to a yes-instance of sparse balancedness (the single-edge signed graph is balanced), so the reduction is not sound. The proof also states that the Combinatorial Hodge Laplacian has a diagonal counting the non-zero entries per row; this is false, since the diagonal entry p+1+deg^up(sigma) is not the number of non-zero off-diagonal entries. Thus the hardness of sparse balancedness is unsupported.
[Section IV.C, Theorem 2] Theorem 2 inherits the failure of Theorem 1. The Zaslavsky negative-subdivision reduction from balancedness to bipartiteness (Proposition 15) is valid, but it is applied to an input whose QMA1-hardness has not been established because Proposition 1 is false. Consequently, the QMA1-hardness of sparse bipartitedness is also unsupported.

minor comments (4)

[Section II.C] Definition 2 for marked sparse access to signed graphs is repeated verbatim in the introduction and again in Section II.C; the duplicate definitions should be renumbered and consolidated.
[Section III.C, Eq. (23)] The notation sng(sigma cap tau, partial sigma) is a typo: the second argument should be sigma, not partial sigma, since the sign function sng is defined on pairs of simplices. The same notational slip appears in the sign formula in Proposition 1.
[Section III.F, proof of Proposition 2] The soundness inequality contains a misplaced parenthesis: it writes <psi|I_notV)|psi> instead of <psi|I_notV|psi>; this should be corrected.
[Abstract] The final sentence, 'as another example of testing properties related to the eigenspace of a stoquastic Hamiltonians are quantumly hard in the sparse input model for the graph', contains a grammatical error and should be rephrased.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness reduction imports QMA1-hardness from an external result, and the paper's own reduction steps do not assume what they prove.

full rationale

I walked the derivation chain. The central hardness claims (Theorems 1 and 2) reduce clique homology to sparse balancedness and then sparse balancedness to sparse bipartitedness. The clique-homology hardness is imported from Crichigno and Kohler [5], an external source whose authors are disjoint from this paper's author list; the same holds for the Zaslavsky negative-subdivision construction [7] used for the balanced-to-bipartite reduction. Proposition 1, the unitary-equivalence claim between the Combinatorial Hodge Laplacian and a signed graph Laplacian, is introduced as an original theorem and proved directly in Section III.C; it does not rely on sparse balancedness, bipartitedness, or on the QMA1-hardness being established. No parameter is fitted to data and later renamed a prediction, and no claim is justified only by a self-citation. The later QMA-containment arguments (Propositions 2 and 3) use standard block-encoding and phase-estimation techniques, again independently derived in the paper. The reader's note that the diagonal computation in the proof of Proposition 1 is mathematically invalid (Eqs. 19-23) is a correctness concern about a non-circular lemma, not an instance of the paper assuming its own conclusion. A false or unproved intermediate claim can invalidate a reduction without making it circular. For that reason, the appropriate circularity score is 0, while the correctness risk of the paper may be substantial on other grounds.

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

No free parameters are fitted to data and no new entities are postulated. The central failure is an incorrect mathematical equivalence, not an added parameter or object.

assumptions (5)

domain assumption Clique homology is QMA1-hard, as proven by Crichigno and Kohler.
Used as the source problem for the reduction in Theorem 1, stated as Proposition 9 in the paper.
standard math The kernel of the p-th Combinatorial Hodge Laplacian is isomorphic to the p-th homology group, as proven by Friedman.
Connects clique homology to kernel nontriviality in the reductions.
standard math A connected signed graph is balanced if and only if the kernel of its signed Laplacian is nontrivial.
Used to translate balancedness to spectral terms, cited to Kunegis et al.
domain assumption Zaslavsky's negative subdivision maps balanced signed graphs to bipartite unsigned graphs.
Basis for the reduction in Theorem 2, cited to Zaslavsky.
standard math Sparse matrices with row and entry oracles admit block encodings.
Used for the QMA containment of the promise variants, cited to Camps et al.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard." pith.science (2026). https://pith.science/paper/DKILUKHV

@misc{pith2026241214932,
  author       = {Pith},
  title        = {Pith review of: Testing the presence of balanced and bipartite components in a sparse graph is QMA1-hard},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DKILUKHV}},
  note         = {Machine review of arXiv:2412.14932}
}

read the original abstract

Determining whether an abstract simplicial complex, a discrete object often approximating a manifold, contains multi-dimensional holes is a task deeply connected to quantum mechanics and proven to be QMA1-hard by Crichigno and Kohler. This task can be expressed in linear algebraic terms, equivalent to testing the non-triviality of the kernel of an operator known as the Combinatorial Laplacian. In this work, we explore the similarities between abstract simplicial complexes and signed or unsigned graphs, using them to map the spectral properties of the Combinatorial Laplacian to those of signed and unsigned graph Laplacians. We prove that our transformations preserve efficient sparse access to these Laplacian operators. Consequently, we show that key spectral properties, such as testing the presence of balanced components in signed graphs and the bipartite components in unsigned graphs, are QMA1-hard. These properties play a paramount role in network science. The hardness of the bipartite test is relevant in quantum Hamiltonian complexity, as another example of testing properties related to the eigenspace of a stoquastic Hamiltonians are quantumly hard in the sparse input model for the graph.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 36 canonical work pages

[1]

S peciﬁcally, the Laplacian of a signed graph is symmetric and takes values in − 1,0,1, whereas the Laplacian of a directed graph is not symmetric a nd takes values in 0,1

Signed graphs should not be confused with directed graphs. S peciﬁcally, the Laplacian of a signed graph is symmetric and takes values in − 1,0,1, whereas the Laplacian of a directed graph is not symmetric a nd takes values in 0,1

work page
[2]

F. R. Chung, Spectral graph theory, Vol. 92 (American Mathematical Soc., 1997)

work page 1997
[3]

Gharibian, Y

S. Gharibian, Y. Huang, Z. Landau, S. W. Shin, et al. , Quantum hamiltonian complexity, Foundations and Trends® in Theoretical Computer Science 10, 159 (2015)

work page 2015
[4]

Adamaszek and J

M. Adamaszek and J. Stacho, Complexity of simplicial homolo gy and independence complexes of chordal graphs, Compu- tational Geometry 57, 8 (2016)

work page 2016
[5]

Crichigno and T

M. Crichigno and T. Kohler, Clique homology is QMA1-hard, ar Xiv preprint arXiv:2209.11793 (2022)

arXiv 2022
[6]

King and T

R. King and T. Kohler, Gapped Clique Homology on weighted gra phs is QMA1-hard and contained in QMA, arXiv preprint arXiv:2311.17234 (2023)

arXiv 2023
[7]

Zaslavsky, Negative (and positive) circles in signed gra phs: A problem collection, AKCE International Journal of Gr aphs and Combinatorics 15, 31 (2018)

T. Zaslavsky, Negative (and positive) circles in signed gra phs: A problem collection, AKCE International Journal of Gr aphs and Combinatorics 15, 31 (2018)

work page 2018
[8]

Figueiredo and Y

R. Figueiredo and Y. Frota, The maximum balanced subgraph of a signed graph: Applications and solution approaches, European Journal of Operational Research 236, 473 (2014)

work page 2014

Show all 42 references

[9]

J. Tang, C. Aggarwal, and H. Liu, Recommendations in signed s ocial networks, in Proceedings of the 25th International Conference on World Wide Web (2016) pp. 31–40

2016
[10]

Y. Tian, S. Lautz, A. O. Wallis, and R. Lambiotte, Extracting complements and substitutes from sales data: a network perspective, EPJ Data Science 10, 45 (2021)

2021
[11]

Vicsek, A

T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, Novel type of phase transition in a system of self-driven particles, Physical review letters 75, 1226 (1995)

1995
[12]

Ou-Yang, D.-Q

L. Ou-Yang, D.-Q. Dai, and X.-F. Zhang, Detecting protein co mplexes from signed protein-protein interaction networks , IEEE/ACM transactions on computational biology and bioinf ormatics 12, 1333 (2015)

2015
[13]

C. W. Reynolds, Flocks, herds and schools: A distributed beh avioral model, in Proceedings of the 14th annual conference on Computer graphics and interactive techniques (1987) pp. 25–34

1987
[14]

Camps, L

D. Camps, L. Lin, R. Van Beeumen, and C. Yang, Explicit quantu m circuits for block encodings of certain sparse matrices, SIAM Journal on Matrix Analysis and Applications 45, 801 (2024)

2024
[15]

Sünderhauf, E

C. Sünderhauf, E. Campbell, and J. Camps, Block-encoding st ructured matrices for data input in quantum computing, Quantum 8, 1226 (2024)

2024
[16]

Barabási and R

A.-L. Barabási and R. Albert, Emergence of scaling in random networks, science 286, 509 (1999)

1999
[17]

Herbert and S

S. Herbert and S. Subramanian, Spectral sparsiﬁcation of ma trix inputs as a preprocessing step for quantum algorithms, arXiv preprint arXiv:1910.02861 (2019)

2019 arXiv
[18]

Apers and R

S. Apers and R. De Wolf, Quantum speedup for graph sparsiﬁcat ion, cut approximation, and laplacian solving, SIAM Journal on Computing 51, 1703 (2022)

2022
[19]

S. P. Jordan, D. Gosset, and P. J. Love, Quantum-merlin-arth ur–complete problems for stoquastic hamiltonians and mark ov matrices, Physical Review A—Atomic, Molecular, and Optica l Physics 81, 032331 (2010)

2010
[20]

Jost and D

J. Jost and D. Zhang, Cheeger inequalities on simplicial com plexes, arXiv preprint arXiv:2302.01069 (2023)

2023
[21]

Goldreich and D

O. Goldreich and D. Ron, Property testing in bounded degree g raphs, in Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (1997) pp. 406–415

1997
[22]

Trevisan, Lecture notes on graph partitioning, expander s and spectral methods, Lecture notes (2016), available at https://lucatrevisan.github.io/books/expanders-2016.pdf

L. Trevisan, Lecture notes on graph partitioning, expander s and spectral methods, Lecture notes (2016), available at https://lucatrevisan.github.io/books/expanders-2016.pdf. 25

2016
[23]

Cvetković, P

D. Cvetković, P. Rowlinson, and S. K. Simić, Signless laplac ians of ﬁnite graphs, Linear Algebra and its applications 423, 155 (2007)

2007
[24]

Lloyd, S

S. Lloyd, S. Garnerone, and P. Zanardi, Quantum algorithms f or topological and geometric analysis of data, Nature communications 7, 10138 (2016)

2016
[25]

McArdle, A

S. McArdle, A. Gilyén, and M. Berta, A streamlined quantum al gorithm for topological data analysis with exponentially fewer qubits, arXiv preprint arXiv:2209.12887 (2022)

2022 arXiv
[26]

D. W. Berry, Y. Su, C. Gyurik, R. King, J. Basso, A. D. T. Barba, A. Rajput, N. Wiebe, V. Dunjko, and R. Babbush, Analyzing prospects for quantum advantage in topological d ata analysis, PRX Quantum 5, 010319 (2024)

2024
[27]

Gyurik, C

C. Gyurik, C. Cade, and V. Dunjko, Towards quantum advantage via topological data analysis, Quantum 6, 855 (2022)

2022
[28]

Schmidhuber and S

A. Schmidhuber and S. Lloyd, Complexity-theoretic limitat ions on quantum algorithms for topological data analysis, P RX Quantum 4, 040349 (2023)

2023
[29]

Cade and P

C. Cade and P. M. Crichigno, Complexity of supersymmetric sy stems and the cohomology problem, Quantum 8, 1325 (2024)

2024
[30]

Gyurik, A

C. Gyurik, A. Schmidhuber, R. King, V. Dunjko, and R. Hayakaw a, Quantum computing and persistence in topological data analysis, arXiv preprint arXiv:2410.21258 (2024)

2024 arXiv
[31]

Bravyi, D

S. Bravyi, D. P. Divincenzo, R. I. Oliveira, and B. M. Terhal, The complexity of stoquastic local hamiltonian problems, arXiv preprint quant-ph/0606140 (2006)

2006 arXiv
[32]

Bravyi, A

S. Bravyi, A. J. Bessen, and B. M. Terhal, Merlin-arthur game s and stoquastic complexity, arXiv preprint quant-ph/0611 021 (2006)

2006
[33]

Aharonov and A

D. Aharonov and A. B. Grilo, Stoquastic pcp vs. randomness, i n 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019) pp. 1000–1023

2019
[34]

A. M. Childs, D. Gosset, and Z. Webb, The bose-hubbard model i s qma-complete, in Automata, Languages, and Pro- gramming: 41st International Colloquium, ICALP 2014, Cope nhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41 (Springer, 2014) pp. 308–319

2014
[35]

C. Cade, M. Folkertsma, S. Gharibian, R. Hayakawa, F. Le Gall , T. Morimae, and J. Weggemans, Improved Hardness Results for the Guided Loca l Hamiltonian Problem, in 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , Leibniz International Pro-...

2023
[36]

Dittrich and G

T. Dittrich and G. Matz, Signal processing on signed graphs: Fundamentals and potentials, IEEE Signal Processing Magazine 37, 86 (2020)

2020
[37]

Kunegis, S

J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. W. De Luc a, and S. Albayrak, Spectral analysis of signed graphs for clustering, prediction and visualization, in Proceedings of the 2010 SIAM international conference on da ta mining (SIAM,

2010
[38]

Lim, Hodge laplacians on graphs, Siam Review 62, 685 (2020)

L.-H. Lim, Hodge laplacians on graphs, Siam Review 62, 685 (2020)

2020
[39]

Friedman, Computing betti numbers via combinatorial lap lacians, in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (1996) pp

J. Friedman, Computing betti numbers via combinatorial lap lacians, in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (1996) pp. 386–391

1996
[40]

She and Z

B. She and Z. Kan, Algebraic topological characterizations of structural balance in signed graphs, Automatica 107, 61 (2019)

2019
[41]

Adriaens and S

F. Adriaens and S. Apers, Testing cluster properties of sign ed graphs, in Proceedings of the ACM Web Conference 2023 (2023) pp. 49–59

2023
[42]

Desai and V

M. Desai and V. Rao, A characterization of the smallest eigen value of a graph, Journal of Graph Theory 18, 181 (1994)

1994

Pith tools

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

[1] [1]

S peciﬁcally, the Laplacian of a signed graph is symmetric and takes values in − 1,0,1, whereas the Laplacian of a directed graph is not symmetric a nd takes values in 0,1

Signed graphs should not be confused with directed graphs. S peciﬁcally, the Laplacian of a signed graph is symmetric and takes values in − 1,0,1, whereas the Laplacian of a directed graph is not symmetric a nd takes values in 0,1

work page

[2] [2]

F. R. Chung, Spectral graph theory, Vol. 92 (American Mathematical Soc., 1997)

work page 1997

[3] [3]

Gharibian, Y

S. Gharibian, Y. Huang, Z. Landau, S. W. Shin, et al. , Quantum hamiltonian complexity, Foundations and Trends® in Theoretical Computer Science 10, 159 (2015)

work page 2015

[4] [4]

Adamaszek and J

M. Adamaszek and J. Stacho, Complexity of simplicial homolo gy and independence complexes of chordal graphs, Compu- tational Geometry 57, 8 (2016)

work page 2016

[5] [5]

Crichigno and T

M. Crichigno and T. Kohler, Clique homology is QMA1-hard, ar Xiv preprint arXiv:2209.11793 (2022)

arXiv 2022

[6] [6]

King and T

R. King and T. Kohler, Gapped Clique Homology on weighted gra phs is QMA1-hard and contained in QMA, arXiv preprint arXiv:2311.17234 (2023)

arXiv 2023

[7] [7]

Zaslavsky, Negative (and positive) circles in signed gra phs: A problem collection, AKCE International Journal of Gr aphs and Combinatorics 15, 31 (2018)

T. Zaslavsky, Negative (and positive) circles in signed gra phs: A problem collection, AKCE International Journal of Gr aphs and Combinatorics 15, 31 (2018)

work page 2018

[8] [8]

Figueiredo and Y

R. Figueiredo and Y. Frota, The maximum balanced subgraph of a signed graph: Applications and solution approaches, European Journal of Operational Research 236, 473 (2014)

work page 2014