arXiv preprint ·
Finding non-bisimplicial and triad-free minimal separators
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles
Quantized six-vertex realizations of frustration graphs
A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes
Degeneracy graph determinants and higher-dimensional Young diagrams
Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.