Algorithm enumerates graph structures much faster than before
Output-linear time enumeration of potential maximal cliques
Data Structures and Algorithms
Summary
Finding certain key groups of nodes, called potential maximal cliques, helps solve important problems about networks like social connections or computer circuits. Until now, listing all these groups took a lot of time, slowing down other useful calculations. The authors developed a new method to list these groups almost as quickly as they appear, speeding up several important tasks in network analysis. This breakthrough could lead to better computer tools for analyzing complex networks.
What this means in practice
- •For graph algorithm developers: Speed up algorithms that compute treewidth by enabling faster enumeration of potential maximal cliques.
- •For network optimization engineers: Enhance tools for finding minimum fill-in and largest induced subgraphs with bounded treewidth using a more efficient way to list key graph structures.
Authors
Pierre Bergé, Vincent Limouzy, Nicolas Schivre
Abstract
First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, {\em i.e.} a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.