The parameterized complexity of counting minimum cuts stands as a natural question because Ball and Provan showed its #P-completeness. For any undirected graph G = (V, E) and two disjoint sets of its vertices S, T, we design a fixed-parameter tractable algorithm which counts minimum edge (S, T)-cuts parameterized by their size p. Our algorithm operates on a transformed graph instance. This transformation, called drainage, reveals a collection of at most n — |V| successive minimum (5, T)-cuts Z_t. We prove that any minimum (S,T)-cut X contains edges of at least one cut Z_i. This observation, together with Menger's theorem, allows us to build the algorithm counting all minimum (S, T)-cuts with running time 2~(O(p~(2)))n~(O(1)). Initially dedicated to counting minimum cuts, it can be modified to obtain an FPT sampling of minimum edge (S,T)-cuts.
展开▼
机译：参数化的最小切割数量的复杂性是一个自然的问题，因为Ball和Provan显示了其#P完整性。对于任何无向图G =（V，E）及其顶点S，T的两个不相交集，我们设计了一个固定参数可处理算法，该算法计算由其大小p参数化的最小边（S，T）切割。我们的算法在变换后的图实例上运行。这种称为排水的转换揭示了最多n个|| V |的集合。连续的最小值（5，T）削减Z_t。我们证明任何最小（S，T）切割X都包含至少一个切割Z_i的边缘。该观察结果与Menger定理一起，使我们能够构建计算运行时间为2〜（O（p（（2）））n〜（O（1））的所有最小（S，T）割的算法。最初专用于计算最小切割，可对其进行修改以获得最小边缘（S，T）切割的FPT采样。
展开▼
