Polynomial algorithms solve middle cases of minimal separator problems
Finding non-bisimplicial and triad-free minimal separators
Data Structures and Algorithms
Summary
Minimal separators are certain groups of nodes in a network that, if removed, break connections between two points. Some special types of these separators are easier or harder to find using computers. The authors solved previously open cases by creating algorithms that quickly decide if every minimal separator can be broken down into two cliques or find a separator without groups of three unrelated nodes. Their work fills gaps between easy and hard cases known before.
What this means in practice
- •For network analysts: Identify critical small groups of nodes that disconnect pairs in communication networks using efficient algorithms.
- •For cybersecurity teams: Find minimal node sets that block communication paths without complex branching to analyze network vulnerabilities.
Authors
Maria Chudnovsky, Ilya Maier
Abstract
A $u\hbox{-}v$ separator in $G$ is a set $S\subseteq V(G)\setminus\{u,v\}$ such that there is no $u\hbox{-}v$ path in $G\setminus S$. A minimal separator in $G$ is a set $S$ such that for some $u,v\in V(G)\setminus S$, $S$ is a $u\hbox{-}v$ separator in $G$ but no proper subset of $S$ is. A set $S$ is bisimplicial if it is the union of at most two cliques. Recognizing graphs in which every minimal separator is the union of at most $k$ cliques is polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We settle the remaining case $k=2$ by giving a polynomial-time algorithm to decide whether every minimal separator in a graph is bisimplicial. A set $S$ is triad-free if its independence number $α(S)$ is at most two. Given a graph $G$ and two vertices $u,v$, the problem of finding a $u\hbox{-}v$ separator $S$ with $α(S)\leq k$ had the same complexity gap: it was known to be polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We resolve the remaining case $k=2$ by giving a polynomial-time algorithm that finds a triad-free $u\hbox{-}v$ separator or determines that none exists.