The Complexity of Mixed-Connectivity

Abstract

We investigate the parameterized complexity in $a$ and $b$ of determining whether a graph~$G$ has a subset of $a$ vertices and $b$ edges whose removal disconnects $G$, or disconnects two prescribed vertices $s,t\in V(G)$.

11 pages, 6 figures