Computing the largest bond of a graph

Um bond de um grafo $G$ é um conjunto desconectante minimal de arestas de $G$, isto é, bonds são conjuntos de corte que correspondem a cortes $[S,V\setminus S]$ de $G$ onde $G[S]$ e $G[V\setminus S]$ são ambos conexos.
Dado $s,t\in V(G)$, um $st$-bond de $G$ é um bond cuja remoção desconecta $s$ e $t$.
Nesse trabalho, nós investigamos a complexidade de se computar o maior bond e maior $st$-bond de um grafo.
Apesar de cortes e bonds serem correlacionados, observamos que computar o maior bond de um grafo tende a ser mais difícil do que computar o seu corte máximo.
Nós mostramos que {\sc Maior Bond} se mantém NP-difícil mesmo para grafos planares bipartidos.
Além disso, apresentamos um framework para reduzir {\sc Corte Máximo} a {\sc Maior Bond}, o qual nos permite identificar diversas classes onde o problema é NP-difícil.
Em relação a complexidade parametrizada, demonstramos que {\sc Maior Bond} e {\sc Maior $st$-Bond} em grafos com clique-width $w$ não podem ser resolvidos em tempo $f(w)\times n^{o(w)}$, a menos que ETH falhe, porém podem ser resolvidos em tempo $f(w)\times n^{O(w)}$. Utilizando minors, também mostramos que os mesmos são FPT quando parametrizados pelo tamanho da solução ou pela treewidth. Por fim, observamos que
tais problemas parametrizados não admitem núcleos polinomiais, a menos que $NP$ $\subseteq$ $coNP/poly$.