New method lists small special cliques in graphs with fixed delay
Enumerating Small Potential Maximal Cliques with Fixed-Parameter Delay
Data Structures and AlgorithmsDatabases
Summary
Finding special groups of connected points called potential maximal cliques in networks helps solve complex problems like measuring how tree-like a network is. The authors present an algorithm that quickly lists all such groups up to a certain size in a graph without duplicates. Their method uses advanced graph decomposition techniques to efficiently handle challenging graph structures. This helps improve exact methods for computing important graph properties.
What this means in practice
- •For graph algorithm engineers: Implement faster exact treewidth and minimum fill-in computations for small subgraphs using the new fixed-delay enumeration of potential maximal cliques.
- •For network analysis tool developers: Improve network structure analysis tools by integrating efficient enumeration of constrained subgraph cliques for feature extraction or preprocessing.
Authors
Batya Kenig
Abstract
A potential maximal clique (PMC) of a graph $G$ is a nonempty vertex set that forms a maximal clique in some minimal triangulation of $G$. Listing the PMCs of a graph is a key step in exact algorithms for computing treewidth, minimum fill-in, and related graph parameters. We present a deterministic algorithm that enumerates all PMCs of cardinality at most $k$ in an $n$-vertex graph $G$, without repetition, with delay $2^{O(k^3)}n^4\log n$. This bound also covers the preprocessing time before the first output, the time from the last output to termination, and the total running time when no such PMC exists. At the core of our enumeration algorithm is a procedure that solves the following constrained search problem within the same time bound: given sets of required and excluded vertices $I,O\subseteq V(G)$, find a PMC $Ω$ of size at most $k$ satisfying $I\subseteqΩ$ and $Ω\cap O=\emptyset$, or determine that none exists. Our enumeration algorithm directly supports these inclusion and exclusion constraints as well. Our approach builds on the \emph{recursive understanding} technique of Chitnis et al.~\cite{chitnis2016} and the reduction to unbreakable graphs of Lokshtanov et al.~\cite{lokshtanov2018}. A graph is $(q,k)$-unbreakable if no removal of at most $k$ vertices leaves two disjoint unions of connected components that each contain more than $q$ vertices. We first solve constrained PMC search on $(q,k)$-unbreakable graphs, and then apply this procedure to replace separated subgraphs with graphs of size $2^{O(k^2)}$ that preserve the existence of a constrained solution for every graph attached along the shared boundary.