论文标题
计算最大键和图的最大连接切割
Computing the Largest Bond and the Maximum Connected Cut of a Graph
论文作者
论文摘要
图$ g =（v，e）$的切割式$ \ partial（s）$是$ s \ subset v $中一个端点的一组，而另一个端点则是$ v \ setminus s $，并且每当连接$ g [s] $时，cut $ cut $ [s，v \ setMinus s of $ g $ of $ g $均为cut a cut a cot a contect a connect a connect a connect a connect a connect a connect a connect a connect。图$ g $的债券是$ g $的最小值断开连接集，即，债券是削减键，可以确定$ [s，v \ setminus s $ $ g $ of $ g $，因此$ g [s] $ g [s] $ g [s] $ g [v \ setMinus s]均连接。与大量与最大削减有关的研究形成鲜明对比，关于一般图最大键的结果很少。在本文中，我们旨在减少计算最大键的复杂性以及图的最大连接切割的差距。尽管切割和键相似，但我们指出，计算最大键和图形的最大连接切割往往比计算最大切割更难。我们表明，除非p = np，否则它不存在计算最大键的恒定因子近似算法。另外，我们表明{\ sc最大键}和{\ sc最大连接的切割}即使对于平面两部分图，也是np-hard，而\ textsc {maximum cut}在两极图上是微不足道的，在平面图上可溶解了多项式时间。此外，我们表明{\ scmives bond}和{\ sc最大连接的切割}是拆分图上的np-hard，并且仅限于clique-width $ w $的图表，它们在时间$ f（w）\ times n^{o（w）} $中无法在时间$ f（w）\ times n^{o（w）} $中求解，除非指定时间假设失败，否则他们可以求解时间$ f。 n^{o（w）} $。最后，我们表明，当通过解决方案的大小，树宽和双覆盖号码进行参数化时，这两个问题都是固定参数。
The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$. Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.
