pith. sign in

arxiv: 2604.28096 · v1 · submitted 2026-04-30 · 💻 cs.DS

Succinct Graph Representations and Algorithmic Applications

Ahammed Ullah , Alex Pothen This is my paper

Pith reviewed 2026-05-07 04:54 UTC · model grok-4.3

classification 💻 cs.DS
keywords dual clique coversuccinct graph representationclique covergraph algorithmsconnected componentsmaximal matchingdense local structurerepresentation-aware algorithms
0
0 comments X

The pith

Dual clique cover representations let graph algorithms run in time proportional to the compact representation size instead of the number of edges.

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

The paper introduces dual clique cover representations for undirected graphs, defined as a pair consisting of a collection of cliques that together cover every edge and the incidence dual of that collection. For graphs that admit succinct versions of these representations, the covers can be constructed in polynomial time while remaining much smaller than the edge set. Representation-aware algorithms are then given for finding connected components, building breadth-first and depth-first search forests, and computing maximal matchings; each runs in time linear in the size of the dual clique cover. When the representation is succinct, the resulting methods match or improve the time and space performance of conventional adjacency-list algorithms. Empirical tests on real-world and synthetic graphs confirm substantial reductions in both memory and total running time.

Core claim

A dual clique cover (DCC) representation of an undirected graph G is the pair (C, L), where C is a collection of cliques covering the edges of G and L is the incidence dual of C. Succinct DCC representations are those that are both compact and constructible in polynomial time. Graph primitives such as connected components, BFS forests, DFS forests, and maximal matchings can be computed in time proportional to the size of any DCC representation. When the representation is succinct, the combined time and space bounds match or improve upon those obtained from standard edge-list representations.

What carries the argument

The dual clique cover (DCC) representation: a clique edge cover C paired with its incidence dual L, which lets algorithms traverse cliques and vertex-clique incidences rather than individual edges.

If this is right

  • Connected components, BFS forests, DFS forests, and maximal matchings are all computable in time linear in the size of the DCC representation.
  • For any graph admitting a succinct DCC, the new algorithms achieve time and space bounds that are at least as good as, and sometimes strictly better than, their adjacency-list counterparts.
  • Construction algorithms for succinct DCC representations run in polynomial time and come with explicit efficiency guarantees.
  • Empirical memory savings reach 35x and total-time speedups reach 35x on tested instances when the representation is succinct.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same representation-aware approach could be adapted to other primitives such as shortest paths or spanning trees whenever those problems can be solved by traversing cliques and incidences.
  • Graphs arising from social or biological networks, which often contain dense communities, are natural candidates for large practical speedups.
  • If succinct DCCs can be maintained under edge insertions or deletions, the framework would extend directly to dynamic graph algorithms.

Load-bearing premise

Many graphs possess dense local clique structure that permits a compact dual clique cover to be found in polynomial time and to be substantially smaller than the edge set.

What would settle it

Constructing a DCC representation on a large collection of graphs and finding that its size is not appreciably smaller than the number of edges, or that construction time exceeds the subsequent algorithmic savings, would show the claimed improvements do not materialize.

Figures

Figures reproduced from arXiv: 2604.28096 by Ahammed Ullah, Alex Pothen.

Figure 1
Figure 1. Figure 1: Two cliques of order n connected by a perfect matching (shown here for n = 7). A dual clique cover (DCC) representation of this graph family requires only Θ (n) space, whereas standard representations such as adjacency lists require Θ view at source ↗
Figure 2
Figure 2. Figure 2: Partial order of minimality properties of clique covers of a graph under logical implication. Properties view at source ↗
Figure 3
Figure 3. Figure 3: Constructing L from C and C from L For efficient black-box queries and for many representation-aware applications (Section 4), it is useful to maintain both C and L. However, for storage or communication, it suffices to keep either C or L, since the other can be constructed as needed in time and space linear in the size of the representation, as illustrated in view at source ↗
Figure 4
Figure 4. Figure 4: An algorithm to compute σ-succinct DCC representations of graphs. In Phase-1, Step 5 initializes C with color classes Fℓ of G of size at least two, and Step 6 updates the sets {Mv} to mark edges internal to these cliques as covered. In Phase-2, Step 8 defines the index set Tv for each vertex v, and Step 9 creates a clique Cv,ℓ for each vertex v and each ℓ ∈ Tv with Fℓ ∩ Mv ̸= ∅. In both phases, Extend (inv… view at source ↗
Figure 5
Figure 5. Figure 5: A subroutine of Algorithm Succinct-Peeling. each Ck is an initial clique Cℓ derived from a color class Fℓ and the pivot edge satisfies {uk, vk} ⊆ Fℓ. Since the color classes are disjoint, all pivot edges used in Phase 1 are distinct. In Phase-2, each Ck = Cv,ℓ is initialized from an uncovered edge {u, v} with u ∈ Fℓ ∩ Mv, and this edge is never reused as a pivot. Thus, over both phases, the pivot edges {uk… view at source ↗
Figure 6
Figure 6. Figure 6: Breadth-first search using a DCC representation. view at source ↗
Figure 7
Figure 7. Figure 7: Depth-first search forest using a DCC representation. Left: the top-level DFS routine initializes the view at source ↗
Figure 8
Figure 8. Figure 8: Connected components using a clique cover. view at source ↗
Figure 9
Figure 9. Figure 9: A maximal matching algorithm using a clique cover. view at source ↗
Figure 10
Figure 10. Figure 10: Succinct DCC construction via global admissibility. view at source ↗
Figure 11
Figure 11. Figure 11: Succinct DCC construction via local coloring and admissibility. view at source ↗
Figure 12
Figure 12. Figure 12: A Subroutine of Algorithm Local-Admissibility. sets and the relevant global M-sets. If Au ∩ Aw = ∅, then it leaves the edge uncovered. This deviation from Step 2 of Algorithm Global-Admissibility is safe because both u and w are in the earlier-neighborhood of vi , hence {u, w} would be processed and ultimately covered by the time the algorithm processes some vj with j < i such that vj is the later endpoin… view at source ↗
Figure 13
Figure 13. Figure 13: Clique-cover compression ratio 2m/ size(C) and construction time for the algorithms in view at source ↗
Figure 14
Figure 14. Figure 14: Read-time and compute-time for connected components (via union–find) using adjacency list and view at source ↗
Figure 15
Figure 15. Figure 15: Total-time for maximal matching (top row) and connected components (bottom row) usingWebGraph view at source ↗
Figure 16
Figure 16. Figure 16: Total-time for maximal matching (top row) and connected components (bottom row) usingWebGraph view at source ↗
Figure 17
Figure 17. Figure 17: An example graph used to illustrate multiple concepts. view at source ↗
Figure 18
Figure 18. Figure 18: Maximal independent set (MIS) using a DCC representation. view at source ↗
Figure 19
Figure 19. Figure 19: First-fit greedy coloring using a DCC representation. view at source ↗
Figure 20
Figure 20. Figure 20: k-Core decomposition using a DCC representation. Lemma B.7. Let RG = (C,L) be a DCC representation of a graph G with clique number ω. Algorithm k-Core￾Decomposition returns the coreness of every vertex of G using O (ω · size(RG)) time and O (size(RG)) space. Proof. For each v ∈ V , let f (v) denote the value assigned to κ (v) when v is peeled by Algorithm k-Core￾Decomposition. We show that f (v) = κ (v) f… view at source ↗
Figure 21
Figure 21. Figure 21: Maximal clique using a DCC representation. view at source ↗
Figure 22
Figure 22. Figure 22: implements this algorithm using a DCC representation of G. As in the first-fit coloring of G, it maintains a color array color (v) initialized to 0, a timestamp counter t, and a variable q storing the number of colors used so far. In contrast to the earlier algorithm, colors are not marked as forbidden. Instead, the algorithm maintains count (z), the number of already-colored vertices currently assigned c… view at source ↗
Figure 23
Figure 23. Figure 23: Clique-cover compression ratio 2m/ size(C) and construction time for the algorithms in view at source ↗
Figure 24
Figure 24. Figure 24: Clique-cover compression ratio 2m/ size(C) and construction time for three algorithms in view at source ↗
Figure 25
Figure 25. Figure 25: Clique-cover compression ratio 2m/ size(C) and construction time for three algorithms in view at source ↗
Figure 26
Figure 26. Figure 26: Clique-cover compression ratio 2m/ size(C) and UB-OPT=2m/ P v∈V ⌈|N(v)| /κ (v)⌉  , an upper bound on the optimal compression ratio. Both y-axes are logarithmic. constant p, we have ω = Θ (log n) with high probability [4]. Therefore, size(C) ≥ 2m/ (ω − 1) = Θ (2m/ log n), so such graphs do not admit compression ratios asymptotically better than Θ (log n). C.3 Detailed Application Performance Section 6.3 r… view at source ↗
read the original abstract

We propose new graph representations that exploit dense local structure to improve time and space simultaneously. Given an undirected graph $G$, we define a dual clique cover (DCC) representation of $G$ to be the pair $(C, L)$, where $C$ is a collection of cliques that covers the edges of $G$ and $L$ is the incidence dual of $C$. We identify classes of polynomial-time constructible DCC representations that are compact and call them succinct DCC representations. We then develop representation-aware algorithms for several fundamental graph problems. We show that graph primitives such as connected components, breadth-first search forests, depth-first search forests, and maximal matchings can be computed in time proportional to the size of a DCC representation rather than the number of edges. Combined with our succinct DCC representations, these results give a class of algorithms that either match or improve the time and space bounds of their counterparts on standard graph representations. Furthermore, we design several algorithms for constructing succinct DCC representations and establish provable guarantees on their efficiency. We evaluate several graph algorithms on DCC representations against adjacency-list-based implementations on a large collection of real-world and synthetic graphs. All evaluated applications show substantial execution memory savings and total-time speedups; for example, the connected components algorithm achieves about $9\times$ execution memory savings on average, with a maximum of $35\times$, and about $6.5\times$ total-time speedups on average, with a maximum of $35\times$. We also evaluate several DCC construction algorithms and find that the succinctness property plays a key role in making DCC representations effective for algorithmic applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper proposes succinct dual clique cover (DCC) representations for undirected graphs, defined as the pair (C, L) where C is an edge-covering collection of cliques and L is the incidence dual. It identifies classes of graphs admitting succinct DCC representations that are compact and constructible in polynomial time. Representation-aware algorithms are developed for connected components, BFS forests, DFS forests, and maximal matchings that run in time proportional to the DCC size rather than the number of edges. The paper also gives construction algorithms with provable efficiency guarantees and reports experimental results on real-world and synthetic graphs showing average 9x memory savings and 6.5x time speedups (with maxima of 35x) for connected components.

Significance. If the claims hold, the work provides a new approach to exploiting dense local structure for simultaneous improvements in time and space for fundamental graph primitives. Strengths include the explicit polynomial-time constructions for specific classes, the direct operation on the incidence structure for the primitives, and the combination of theoretical bounds with empirical validation on real graphs. This could influence algorithm design for graphs with community or clique-like substructures and offers a concrete alternative to standard adjacency-list representations when the succinctness property applies.

major comments (2)
  1. [§4.1] §4.1, Theorem 4.1: The connected-components algorithm is claimed to run in time linear in the DCC size using union-find over cliques; however, the analysis does not explicitly bound the cost when vertices participate in many cliques (i.e., high degree in L), which could introduce an extra factor linear in the maximum number of cliques per vertex and undermine the 'proportional to representation size' claim.
  2. [§3.3] §3.3, Construction for chordal graphs: The polynomial-time claim for building a succinct DCC relies on a linear-time clique enumeration step, but the paper does not address how the incidence dual L is materialized without an extra O(log n) factor per incidence when using standard data structures; this detail is load-bearing for the 'polynomial-time constructible' guarantee.
minor comments (3)
  1. [Figure 2] Figure 2: The illustration of the incidence dual L would benefit from explicit vertex and clique labels to make the traversal for BFS/DFS clearer.
  2. [§6] §6: The experimental section reports averages over 'a large collection' but does not list the exact number of graphs or the selection criteria; adding this would improve reproducibility.
  3. [Abstract] Abstract and §1: The phrase 'time proportional to the size of a DCC representation' is used without an initial formal definition of representation size; a short parenthetical (e.g., |C| + |L|) would help readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's detailed comments, which have helped us improve the clarity of our presentation. Below we respond to each major comment and indicate the revisions made to the manuscript.

read point-by-point responses

  1. Referee: [§4.1] §4.1, Theorem 4.1: The connected-components algorithm is claimed to run in time linear in the DCC size using union-find over cliques; however, the analysis does not explicitly bound the cost when vertices participate in many cliques (i.e., high degree in L), which could introduce an extra factor linear in the maximum number of cliques per vertex and undermine the 'proportional to representation size' claim.

    Authors: The representation size of the DCC is |C| + |L|, with |L| denoting the total number of incidences between vertices and cliques. The connected-components procedure examines each clique and, for each vertex in the clique, performs a union operation. Since each incidence appears exactly once in L, the algorithm performs a constant amount of work per element of L (amortized, via the union-find structure). Thus the running time is O(|L| α(n)), which is linear in the size of the representation. The multiplicity of cliques per vertex is already reflected in the magnitude of |L| and does not introduce an additional multiplicative factor. We have inserted a clarifying sentence immediately after the statement of Theorem 4.1 to make this accounting explicit. revision: yes

  2. Referee: [§3.3] §3.3, Construction for chordal graphs: The polynomial-time claim for building a succinct DCC relies on a linear-time clique enumeration step, but the paper does not address how the incidence dual L is materialized without an extra O(log n) factor per incidence when using standard data structures; this detail is load-bearing for the 'polynomial-time constructible' guarantee.

    Authors: The linear-time clique enumeration for chordal graphs outputs each clique as an explicit list of its vertices. To assemble the incidence dual L we allocate an array of n dynamic lists and, for every vertex belonging to a clique, append the clique identifier to the corresponding list. When dynamic arrays are employed, each append costs amortized constant time; consequently the materialization of L requires only O(|L|) time in total and introduces no logarithmic factor per incidence. The overall construction therefore remains linear in the combined size of the output representation. We have added a paragraph in §3.3 describing the data structures used for this step. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper introduces a new DCC representation defined as the pair (C, L) where C is an edge-covering clique collection and L its incidence dual. It then explicitly identifies specific graph classes admitting polynomial-time constructible compact DCCs, supplies concrete construction algorithms with proven efficiency bounds, and derives representation-aware algorithms for connectivity, BFS/DFS forests, and maximal matchings whose running times are proven linear in |DCC| via direct operations on the incidence structure. All steps rest on independent definitions, standard graph-theoretic arguments, and explicit constructions rather than any reduction to fitted parameters, self-referential equations, or load-bearing self-citations. The experimental section reports measured speedups on real graphs when the succinctness property holds, but these are empirical observations, not part of the claimed derivation. The central claims therefore remain self-contained against external benchmarks and do not collapse by construction to their inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work relies on standard graph theory definitions with no fitted numerical parameters; the key assumption is the existence of polynomial-time succinct DCCs for relevant graph classes, which is a domain assumption rather than an ad hoc invention.

axioms (2)
  • standard math Undirected graphs admit clique edge covers
    Basic definition invoked in the DCC construction.
  • domain assumption Polynomial-time constructible succinct DCCs exist for graphs with dense local structure
    Central to the claim that the representation is compact and usable for algorithmic speedups.
invented entities (1)
  • Dual clique cover (DCC) representation no independent evidence
    purpose: Compact graph representation using clique cover and incidence dual to enable representation-aware algorithms
    Newly defined construct in the paper; no independent external evidence beyond the definition and claimed algorithmic benefits.

pith-pipeline@v0.9.0 · 5589 in / 1575 out tokens · 148916 ms · 2026-05-07T04:54:01.237900+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

74 extracted references · 9 canonical work pages · 1 internal anchor

  1. [1]

    Statistical mechanics of complex networks.Reviews of Modern Physics, 74(1):47, 2002

    Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks.Reviews of Modern Physics, 74(1):47, 2002

    2002

  2. [2]

    Surveyandtaxonomyoflosslessgraphcompressionandspace-efficient graph representations.arXiv preprint arXiv:1806.01799, 2018

    MaciejBestaandTorstenHoefler. Surveyandtaxonomyoflosslessgraphcompressionandspace-efficient graph representations.arXiv preprint arXiv:1806.01799, 2018

    work page arXiv 2018

  3. [3]

    TheWebGraphframeworkI:compressiontechniques

    PaoloBoldiandSebastianoVigna. TheWebGraphframeworkI:compressiontechniques. InProceedingsof the 13th International Conference on World Wide Web, pages 595–602, 2004

    2004

  4. [4]

    Cliques in random graphs.Mathematical Proceedings of the Cambridge Philosophical Society, 80(3):419–427, 1976

    Béla Bollobás and Paul Erdős. Cliques in random graphs.Mathematical Proceedings of the Cambridge Philosophical Society, 80(3):419–427, 1976

    1976

  5. [5]

    A scalable pattern mining approach to web graph compression with communities

    Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression with communities. InProceedings of the 2008 international conference on web search and data mining, pages 95–106, 2008. 29

    2008

  6. [6]

    On the tree-degree of graphs

    Maw-Shang Chang and Haiko Müller. On the tree-degree of graphs. InInternational Workshop on Graph- Theoretic Concepts in Computer Science, pages 44–54. Springer, 2001

    2001

  7. [7]

    AksharChavan,SanazRabinia,DanielGrosu,andMarcoBrocanelli.Acliquepartitioning-basedalgorithm for graph compression.arXiv preprint arXiv:2502.02477, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  8. [8]

    Arboricity and subgraph listing algorithms.SIAM Journal on computing, 14(1):210–223, 1985

    Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms.SIAM Journal on computing, 14(1):210–223, 1985

    1985

  9. [9]

    Large-scale clique cover of real-world networks

    Alessio Conte, Roberto Grossi, and Andrea Marino. Large-scale clique cover of real-world networks. Information and Computation, 270:104464, 2020

    2020

  10. [10]

    MIT press, 2022

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.Introduction to Algorithms. MIT press, 2022

    2022

  11. [11]

    The University of Florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011

    Timothy A Davis and Yifan Hu. The University of Florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011

    2011

  12. [12]

    Assignment-minimum clique coverings.Journal of Experimental Algorithmics (JEA), 17:1–1, 2012

    John M Ennis, Charles M Fayle, and Daniel M Ennis. Assignment-minimum clique coverings.Journal of Experimental Algorithmics (JEA), 17:1–1, 2012

    2012

  13. [13]

    The representation of a graph by set intersections

    Paul Erdős, Adolph W Goodman, and Louis Pósa. The representation of a graph by set intersections. Canadian Journal of Mathematics, 18:106–112, 1966

    1966

  14. [14]

    On the evolution of random graphs.Publ

    Paul Erdős and Alfréd Rényi. On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci., 5:17–60, 1960

    1960

  15. [15]

    Clique partitions, graph compression and speeding-up algorithms

    Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. Journal of Computer and System Sciences, 51(2):261–272, 1995.doi:10.1006/jcss.1995.1065

    work page doi:10.1006/jcss.1995.1065 1995

  16. [16]

    Graphdistances in the data-stream model.SIAM Journal on Computing, 38(5):1709–1727, 2009

    JoanFeigenbaum,SampathKannan,AndrewMcGregor,SiddharthSuri,andJianZhang. Graphdistances in the data-stream model.SIAM Journal on Computing, 38(5):1709–1727, 2009

    2009

  17. [17]

    Edge clique partition and cover beyond independence

    Fedor V Fomin, Petr A Golovach, Danil Sagunov, and Kirill Simonov. Edge clique partition and cover beyond independence. In33rd Annual European Symposium on Algorithms (ESA 2025), pages 43:1–43:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025

    2025

  18. [18]

    Data reduction, exact, and heuristic algo- rithmsforcliquecover

    Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Data reduction, exact, and heuristic algo- rithmsforcliquecover. InProceedingsoftheMeetingonAlgorithmEngineering&Expermiments,pages86–94. Society for Industrial and Applied Mathematics, 2006

    2006

  19. [19]

    Constructing an indeterminate string from its associated graph.Theoretical Computer Science, 710:88–96, 2018

    Joel Helling, PJ Ryan, WF Smyth, and Michael Soltys. Constructing an indeterminate string from its associated graph.Theoretical Computer Science, 710:88–96, 2018

    2018

  20. [20]

    Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

    Anthony Hevia, Benjamin Kallus, Summer McClintic, Samantha Reisner, Darren Strash, and Johnathan Wilson.Solvingedgecliquecoverexactlyviasynergisticdatareduction.In31stAnnualEuropeanSymposium on Algorithms (ESA 2023), pages 61:1–61:19. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

    2023

  21. [21]

    Complexity of graph covering problems for graphs of low degree.Journal of Combina- torial Mathematics and Combinatorial Computing, 11:187–208, 1992

    Douglas N Hoover. Complexity of graph covering problems for graphs of low degree.Journal of Combina- torial Mathematics and Combinatorial Computing, 11:187–208, 1992

    1992

  22. [22]

    Space lower bounds for approximating maximum matching in the edge arrival model

    Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1874–1893. SIAM, 2021

    2021

  23. [23]

    Speeding up algorithms on compressed web graphs

    Chinmay Karande, Kumar Chellapilla, and Reid Andersen. Speeding up algorithms on compressed web graphs. InProceedings of the Second ACM International Conference on Web Search and Data Mining, pages 272–281, 2009

    2009

  24. [24]

    Determination of keyword conflict.IBM Technical Disclosure Bulletin, 16(2):544–546, 1973

    Eduardo Kellerman. Determination of keyword conflict.IBM Technical Disclosure Bulletin, 16(2):544–546, 1973. 30

    1973

  25. [25]

    Kou, Larry J

    Lawrence T. Kou, Larry J. Stockmeyer, and Chak-Kuen Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs.Communications of the ACM, 21(2):135–139, 1978

    1978

  26. [26]

    On covering of graphs

    László Lovász. On covering of graphs. InTheory of Graphs (Proc. Colloq., Tihany, 1966), pages 231–236. Academic Press New York, 1968

    1966

  27. [27]

    Onthehardnessofapproximatingminimizationproblems.Journal of the ACM (JACM), 41(5):960–981, 1994

    CarstenLundandMihalisYannakakis. Onthehardnessofapproximatingminimizationproblems.Journal of the ACM (JACM), 41(5):960–981, 1994

    1994

  28. [28]

    Clique covering of chordal graphs.Utilitas Mathematica, 36:151–152, 1989

    Shaohan Ma, Walter D Wallis, and Julin Wu. Clique covering of chordal graphs.Utilitas Mathematica, 36:151–152, 1989

    1989

  29. [29]

    Neuro-causal factor analysis.arXiv preprint arXiv:2305.19802, 2023

    Alex Markham, Mingyu Liu, Bryon Aragam, and Liam Solus. Neuro-causal factor analysis.arXiv preprint arXiv:2305.19802, 2023

    work page arXiv 2023

  30. [30]

    Smallest-lastorderingandclusteringandgraphcoloringalgorithms

    DavidWMatulaandLelandLBeck. Smallest-lastorderingandclusteringandgraphcoloringalgorithms. Journal of the ACM (JACM), 30(3):417–427, 1983

    1983

  31. [31]

    Empoweringfaculty: Acampuscyberinfrastructure strategy for research communities.Educause Review, 2014

    GerryMcCartney, ThomasHacker, andBaijianYang. Empoweringfaculty: Acampuscyberinfrastructure strategy for research communities.Educause Review, 2014

    2014

  32. [32]

    SIAM, 1999

    Terry A McKee and Fred R McMorris.Topics in intersection graph theory. SIAM, 1999

    1999

  33. [33]

    Contentment in graph theory: covering graphs with cliques

    James Orlin. Contentment in graph theory: covering graphs with cliques. InIndagationes Mathematicae (Proceedings), volume 80, pages 406–424. Elsevier, 1977

    1977

  34. [34]

    Totalvariationerrorboundsforgeometricapproximation

    ErolAPeköz,AdrianRöllinn,andNathanRoss. Totalvariationerrorboundsforgeometricapproximation. Bernoulli, 19(2):610–632, 2013

    2013

  35. [35]

    An algorithm for a letter-based representation of all-pairwise comparisons.Journal of Computational and Graphical Statistics, 13(2):456–466, 2004

    Hans-Peter Piepho. An algorithm for a letter-based representation of all-pairwise comparisons.Journal of Computational and Graphical Statistics, 13(2):456–466, 2004

    2004

  36. [36]

    Clique covering and clique partition in generalizations of line graphs.Discrete applied mathematics, 56(1):93–98, 1995

    Erich Prisner. Clique covering and clique partition in generalizations of line graphs.Discrete applied mathematics, 56(1):93–98, 1995

    1995

  37. [37]

    Clique coverings of graphs—a survey

    Norman J Pullman. Clique coverings of graphs—a survey. InCombinatorial Mathematics X: Proceedings of the Conference held in Adelaide, Australia, August 23–27, 1982, pages 72–85. Springer, 2006

    1982

  38. [38]

    Fred S. Roberts. Applications of edge coverings by cliques.Discret. Appl. Math., 10(1):93–109, 1985. doi:10.1016/0166-218X(85)90061-7

    work page doi:10.1016/0166-218x(85)90061-7 1985

  39. [39]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. InAAAI, 2015. URL:https://networkrepository.com

    2015

  40. [40]

    Clique cover of graphs with bounded degeneracy.CoRR, abs/2108.09851, 2021

    Ahammed Ullah. Clique cover of graphs with bounded degeneracy.CoRR, abs/2108.09851, 2021

    work page arXiv 2021

  41. [41]

    Computing clique cover with structural parameterization.arXiv preprint arXiv:2208.12438, 2022

    Ahammed Ullah. Computing clique cover with structural parameterization.arXiv preprint arXiv:2208.12438, 2022

    work page arXiv 2022

  42. [42]

    Weighted matching in a poly-streaming model

    Ahammed Ullah, SM Ferdous, and Alex Pothen. Weighted matching in a poly-streaming model. In 33rd Annual European Symposium on Algorithms (ESA 2025), pages 17:1–17:18. Schloss Dagstuhl–Leibniz- Zentrum für Informatik, 2025

    2025

  43. [43]

    W2SAT: Learning to generate SAT instances from weighted literal incidence graphs.arXiv preprint arXiv:2302.00272, 2023

    Weihuang Wen and Tianshu Yu. W2SAT: Learning to generate SAT instances from weighted literal incidence graphs.arXiv preprint arXiv:2302.00272, 2023

    work page arXiv 2023

  44. [44]

    HyperPLR: Hypergraph generation through projection, learning, and reconstruction

    Weihuang Wen and Tianshu Yu. HyperPLR: Hypergraph generation through projection, learning, and reconstruction. InThe Thirteenth International Conference on Learning Representations, 2025

    2025

  45. [45]

    A fixed-parameter tractable algorithm for combinatorial filter reduction

    Yulin Zhang and Dylan A Shell. A fixed-parameter tractable algorithm for combinatorial filter reduction. arXiv preprint arXiv:2309.06664, 2023. 31 A Deferred Details: Representation Design and Construction A.1 Minimality Landscape: Partial Order Details Composition-minimal=⇒Inclusion-minimal.If no pair of cliquesC i, Cj ∈ Cwithi̸=jcan be merged into a sin...

    work page arXiv 2023

  46. [46]

    InitializeS←∅, andV← S Cℓ∈C Cℓ

  47. [47]

    SetI v ←0, for allv∈V

  48. [48]

    (b) For eachk∈L v do i

    For eachv∈VwithI v = 0do (a) SetS←S∪ {v}. (b) For eachk∈L v do i. SetI u ←1, for allu∈C k

  49. [49]

    Figure 18: Maximal independent set (MIS) using a DCC representation

    ReturnS. Figure 18: Maximal independent set (MIS) using a DCC representation. Fixavertexx̸∈S. Whentheouterloopreachesx,wehaveI x = 1,otherwiseStep3(a)wouldhaveincluded xinS. The variableI x can become1only in Step 3(b)(i), so there exists a previously selected vertexv∈Sand k∈L v such thatx∈C k and Step 3(b)(i) setIx ←1while processingC k. Since{v, x} ⊆C k...

  50. [51]

    Setcolor (v)←0, for allv∈V

  51. [52]

    Sett←1, andmark (z)←0, for allz∈[1,|V|]

  52. [54]

    For eachu∈C ℓ withcolor (u)>0domark (color (u))←t

    For eachv∈Vin the orderπdo (a) For eachℓ∈L v do i. For eachu∈C ℓ withcolor (u)>0domark (color (u))←t. (b) Setp←1/* smallest color */ (c) Whilep≤qandmark (p) =tdop←p+ 1. (d) Ifp > q, then setq←q+ 1. (e) Setcolor (v)←pandt←t+ 1

  53. [55]

    Figure 19: First-fit greedy coloring using a DCC representation

    Return{color (v)} v∈V. Figure 19: First-fit greedy coloring using a DCC representation. Proof.Consider any edge{x, y} ∈E. WLOG, assumexappears earlier thanyin the orderπ. When the algorithm processesy, the vertexxis already colored. SinceCcovers all edges, there exists a cliqueCℓ⋆ ∈ C with{x, y} ⊆C ℓ⋆; equivalently,ℓ⋆ ∈L y andx∈C ℓ⋆. Therefore, while scan...

  54. [56]

    InitializeV← S Cℓ∈C Cℓ

  55. [57]

    Setκ(v)←0,I v ←1,deg c (v)←0, andseen (v)←0, for allv∈V

  56. [58]

    (b) For eachℓ∈L v do i

    For eachv∈Vdo (a) Sett←t+ 1. (b) For eachℓ∈L v do i. For eachu∈C ℓ \ {v}withseen (u)̸=tdo setseen (u)←tand incrementdeg c (v)by1

  57. [59]

    Insert each vertexv∈Vinto a degree bucket keyed bydegc (v)

  58. [60]

    (b) Setκ(v)←deg c (v),I v ←0, andt←t+ 1

    Fori= 1to|V|do (a) ExtractavertexvwithI v = 1andminimumcurrentvaluedeg c (v). (b) Setκ(v)←deg c (v),I v ←0, andt←t+ 1. (c) For eachℓ∈L v do i. For eachu∈C ℓ \ {v}withI u = 1do A. Ifseen (u) =t, continue to the nextu. B. Setseen (u)←t. C. Ifdeg c (u)>deg c (v), then decrementdeg c (u)by1and moveutothedegreebucketkeyedbytheupdateddeg c (u)

  59. [61]

    Figure 20:k-Core decomposition using a DCC representation

    Return{κ(v)} v∈V. Figure 20:k-Core decomposition using a DCC representation. Lemma B.7.LetR G = (C,L)be a DCC representation of a graphGwith clique numberω. Algorithmk-Core- Decompositionreturns the coreness of every vertex ofGusingO(ω·size(RG))time andO(size(R G))space. Proof.For eachv∈V, letf (v)denote the value assigned toκ(v)whenvis peeled by Algorith...

  60. [62]

    InitializeS←arg max Cℓ∈C {|Cℓ|}

  61. [63]

    Select a vertexx∈S, and setA← S ℓ∈Lx Cℓ \S

  62. [64]

    For eachv∈Sdo (a) SetA← {u∈A|L u ∩L v ̸=∅}

  63. [65]

    (b) SetA← {u∈A|L u ∩L v ̸=∅}

    WhileAis nonempty do (a) Selectavertexv∈A,andsetA←A\{v},S←S∪{v}. (b) SetA← {u∈A|L u ∩L v ̸=∅}

  64. [66]

    Figure 21: Maximal clique using a DCC representation

    ReturnS. Figure 21: Maximal clique using a DCC representation. LemmaB.12.LetR G = (C,L)beaDCCrepresentationofagraphGwithcliquenumberω. AlgorithmMaximal-Clique returns a maximal clique ofGinO(ω·size(R G))time usingO(size(R G))space. Proof.The algorithm starts with a cliqueS∈ C. By construction,A=N(x)\Sfor some vertexx∈S. After Step3,thesetA⊆ T v∈S N(v) \S....

  65. [67]

    /*π:=⟨v 1,

    InitializeV← S Cℓ∈C Cℓ. /*π:=⟨v 1, . . . , v|V| ⟩is an ordering ofV.*/

  66. [68]

    Setcolor (v)←0andseen (v)←0, for allv∈V

  67. [69]

    Sett←1, andmark (z)←0,count (z)←0,rem (z)←0, for allz∈[1,|V|]

  68. [70]

    /* number of colors used */

    Setq←0. /* number of colors used */

  69. [71]

    For eachu∈C ℓ withcolor (u)>0do A

    For eachv∈Vin the orderπdo (a) Setp←q+ 1/* start beyond all colors used */ (b) For eachℓ∈L v do i. For eachu∈C ℓ withcolor (u)>0do A. Ifseen (u) =t, then continue to the nextu. B.seen (u)←t. C. Ifmark (color (u))< t, then setrem (color (u))←count (color (u)). D. Setrem (color (u))←rem (color (u))−1andmark (color (u))←t. E. Ifrem (color (u)) = 0, then setp...

  70. [72]

    Figure 22: First-fit greedy coloring ofGusing a DCC representation ofG

    Return{color (v)} v∈V. Figure 22: First-fit greedy coloring ofGusing a DCC representation ofG. Lemma B.13.LetR G = (C,L)be a DCC representation of a graphG= (V, E)with clique numberω, and letπbe an ordering ofV. AlgorithmFirst-Fit-Complement-Coloringreturns the first-fit coloring ofGwith respect toπusing O(ω·size(R G))time andO(size(R G))space. Proof.Cons...

    2009

  71. [73]

    They also improved the size bound, but the resulting covers remain support-minimal

    analyzed the construction of [24] together with the post-processing of [25] and improved the runtime. They also improved the size bound, but the resulting covers remain support-minimal. [9] studied several construction algorithms under a common framework that repeatedly selects an uncovered edge and grows a clique around it. Their constructions ensure tha...

  72. [74]

    proposed a construction that starts with a single clique containing all vertices and processes the non- edges sequentially. For each non-edge{u, v}, every current clique containing bothuandvis replaced by two copies, one withuremoved and the other withvremoved, followed by the deletion of absorbed cliques. This produces composition-minimal covers. On the ...

  73. [75]

    Since each label induces a clique, obtaining clique covers from the label sets is straightforward

    constructs a vertex-label assignment in which adjacent vertices share a label and non-adjacent vertices do not. Since each label induces a clique, obtaining clique covers from the label sets is straightforward. Their algorithm works by exploring maximal cliques and assigning the same label to all vertices in such a clique. Consequently, the resulting cove...

  74. [76]

    However, the limitations of sequential streaming settings persistinthisintegrationaswell

    show that streaming support can be integrated into parallel computation, combining the benefits of small-space computation with parallel speedups. However, the limitations of sequential streaming settings persistinthisintegrationaswell. DCC-baseddesignmayhelpaddresssomeoftheselimitationsforcomputation on static graphs. Hence, designing a new class of repr...