  In the bounded-degree cut problem, we are given a multigraph $G=(V,E)$, two
disjoint vertex subsets $A,B\subseteq V$, two functions $\mathrm{u}_A,
\mathrm{u}_B:V\to \{0,1,\ldots,|E|\}$ on $V$, and an integer $k\geq 0$. The
task is to determine whether there is a minimal $(A,B)$-cut $(V_A,V_B)$ of size
at most $k$ such that the degree of each vertex $v\in V_A$ in the induced
subgraph $G[V_A]$ is at most $\mathrm{u}_A(v)$ and the degree of each vertex
$v\in V_B$ in the induced subgraph $G[V_B]$ is at most $\mathrm{u}_B(v)$. In
this paper, we show that the bounded-degree cut problem is fixed-parameter
tractable by giving a $2^{18k}|G|^{O(1)}$-time algorithm. This is the first
single exponential FPT algorithm for this problem. The core of the algorithm
lies two new lemmas based on important cuts, which give some upper bounds on
the number of candidates for vertex subsets in one part of a minimal cut
satisfying some properties. These lemmas can be used to design fixed-parameter
tractable algorithms for more related problems.
