Complessità di trovare set tagli di dimensioni esatte nei grafici bipartiti

Question

Sono interessato al problema di decidere se un taglio di una determinata dimensione $ k $ (cioè il numero di bordi che attraversano le partizioni è $ k $) esiste in un dato grafico bipartito (sia il grafico che $ k $ fanno parte dell'input). Si noti che questo è diverso dai problemi di Mincut e Maxcut che chiedono semplicemente di trovare i tagli minimi e massimi di dimensioni.

Per i grafici generali, il problema del mincut può essere risolto nel tempo polinomiale mentre il problema di Maxcut è np-hard. Ne consegue che decidere se esiste un cutset di una dimensione particolare in un grafico generale è np-hard poiché potremmo usarlo per trovare il taglio massimo di dimensioni.

Per i grafici bipartiti, tuttavia, il problema di Maxcut è banale: tutti i bordi nel grafico costituiscono il maxcut. Inoltre, se aiuta, penso di poter dimostrare che per i grafici bipartiti, il bordo - il complemento di un taglio è anche un taglio. Questo è se $ E_c sottoseteq e $ è un taglio di un grafico bipartito $ G = (U Cup V, E) $ poi $ E-e_c $ è anche un taglio di $ G $.

Tuttavia, non sono stato in grado di determinare se decidere se un cutset di una certa dimensione $ k $ Esiste è in P o è NP-completo o qualcos'altro. Se è NP-completo, esiste una famiglia di grafici per la quale è in P? Eventuali suggerimenti saranno utili.