In this work, we propose a novel framework for graph canonisation called Hyperset Individualisation, using bisimulation on a set-theoretic framework in an effort to tackle the Graph Isomorphism problem on simple graphs. Building on this idea, we define algorithm HID, which we prove to be strictly more expressive than colour refinement. Moreover, we define two versions of a 𝑘-dimensional HID, which we prove to have different expressive power.
Hyperset Individualisation Algorithms
Simone Boscaratto
;Francesco Nascimben
;Alberto Policriti
2025-01-01
Abstract
In this work, we propose a novel framework for graph canonisation called Hyperset Individualisation, using bisimulation on a set-theoretic framework in an effort to tackle the Graph Isomorphism problem on simple graphs. Building on this idea, we define algorithm HID, which we prove to be strictly more expressive than colour refinement. Moreover, we define two versions of a 𝑘-dimensional HID, which we prove to have different expressive power.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
paper25.pdf
accesso aperto
Descrizione: ICTCS 2025 published version
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
1.37 MB
Formato
Adobe PDF
|
1.37 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
