# DisjointCliqueCover.jl

## Description

This package DisjointCliqueCover, written in the Julia language, implements a method to estimate a minimal *edge-disjoint edge clique cover (EECC)* of a graph, according to the heuristic presented in Burgio et al. [1]. A minimal edge clique cover is a minimal set of cliques able to cover the entire set of edges in the graph. In a EECC, the cliques are required to be all edge-disjoint, i.e., they can have no more than one node in common.

A graph can admit multiple minimal edge clique covers and finding one of them is known to be a NP-complete problem [2]. Therefore, approximate heuristics are needed to estimate it in large graphs.

The notion of EECC is introduced in [1] as a basis to define the Microscopic Epidemic Clique Equations (MECLE) model. This is a discrete-time markovian model describing complex contagion processes on higher-order networks, represented as hypergraphs and, specifically, as simplicial complexes. The model builds upon the cliques in the underlying graph of a considered higher-order network. As shown in [1], in order to account for the higher-order dynamical correlations among the states of the nodes in those cliques, the latter are required to be edje-disjoint. This leads to the search for the EECC of the underlying graph, hence to the respective heuristic whose source code is here provided.

As an example, the following graph admits a unique minimal EECC

which is given by

[2, 4, 13, 14] [3, 4, 5] [6, 7, 13] [8, 9, 13] [9, 10, 11] [1, 2] [1, 14] [7, 8] [11, 12] [12, 13]

## References

Giulio Burgio, Alex Arenas, Sergio Gómez and Joan T. Matamalas: Network clique cover approximation to analyze complex contagions through group interactions,

*Comms. Phys.*(2021) in press (arXiv:2101.03618)Lawrence T. Kou, Larry J. Stockmeyer and Chak Kuen Wong: Covering edges by cliques with regard to keyword conflicts and intersection graphs,

*Comms. ACM***21**(2) (1978) 135–139 (doi)

## Authors

Giulio Burgio (Universitat Rovira i Virgili, Tarragona, Spain)

Alex Arenas (Universitat Rovira i Virgili, Tarragona, Spain)

Sergio Gómez (Universitat Rovira i Virgili, Tarragona, Spain)

Joan T. Matamalas (Harvard Medical School & Brigham and Women's Hospital, Boston, USA)