On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914363527397376 |
|---|---|
| author | Onofri, Elia |
| author_facet | Onofri, Elia |
| contents | Graphs are a fundamental abstraction in computer science and discrete mathematics, where information is encoded in their combinatorial structure. Graph-reduction techniques aim at simplifying graphs while preserving selected structural properties, typically by grouping vertices and replacing each group with a representative, yielding a contracted graph.
A common instance of this paradigm arises when vertices carry categorical information, formalised as a colouring of the vertex set. In this setting, natural contraction units correspond to connected components of vertices sharing the same colour.
In this work, we provide a rigorous mathematical formalisation of $γ$-contraction, a colour-based graph contraction operation. We interpret $γ$-contraction as a quotient-like construction that preserves categorical connectivity, and clarify its relationship with classical notions of graph contraction and quotient graphs. To support a constructive and algorithmic treatment, we introduce a locally-defined iterative variant, termed $β$-contraction, which captures the core mechanism underlying $γ$-contraction.
Building on this framework, we analyse the contraction process from a theoretical perspective and establish formal guarantees of correctness and convergence. In particular, we prove that $β$-contraction converges in a logarithmic number of iterations to $γ$-contraction, and that this bound is asymptotically tight, with base equal to the golden ratio. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12080 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction Onofri, Elia Data Structures and Algorithms Combinatorics 05C75, 05C40, 68R10, 05C85 Graphs are a fundamental abstraction in computer science and discrete mathematics, where information is encoded in their combinatorial structure. Graph-reduction techniques aim at simplifying graphs while preserving selected structural properties, typically by grouping vertices and replacing each group with a representative, yielding a contracted graph. A common instance of this paradigm arises when vertices carry categorical information, formalised as a colouring of the vertex set. In this setting, natural contraction units correspond to connected components of vertices sharing the same colour. In this work, we provide a rigorous mathematical formalisation of $γ$-contraction, a colour-based graph contraction operation. We interpret $γ$-contraction as a quotient-like construction that preserves categorical connectivity, and clarify its relationship with classical notions of graph contraction and quotient graphs. To support a constructive and algorithmic treatment, we introduce a locally-defined iterative variant, termed $β$-contraction, which captures the core mechanism underlying $γ$-contraction. Building on this framework, we analyse the contraction process from a theoretical perspective and establish formal guarantees of correctness and convergence. In particular, we prove that $β$-contraction converges in a logarithmic number of iterations to $γ$-contraction, and that this bound is asymptotically tight, with base equal to the golden ratio. |
| title | On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction |
| topic | Data Structures and Algorithms Combinatorics 05C75, 05C40, 68R10, 05C85 |
| url | https://arxiv.org/abs/2404.12080 |