최대 컷

그래프의 경우 최대 절단은 크기가 적어도 다른 절단과 같은 절개입니다.즉, 그래프의 정점을 2개의 상보 집합 S와 T로 분할하여 S와 T 사이의 가장자리 수가 가능한 한 커지도록 합니다.이러한 절단을 발견하는 것을 최대 절단 문제라고 합니다.

그 문제는 다음과 같이 간단히 말할 수 있다.S와 상보 서브셋 사이의 가장자리 수가 가능한 한 클 수 있도록 정점 집합의 부분 집합 S를 원한다.마찬가지로, 가능한 한 많은 모서리를 가진 그래프의 초당적 하위 그래프를 원합니다.

가중치 최대 컷이라고 불리는 문제의 보다 일반적인 버전이 있습니다.여기서 각 에지는 실수와 그 무게에 관련지어지며, 목적은 에지의 수가 아니라 S와 그 보완 사이에 있는 에지의 총 무게를 최대화하는 것입니다.양의 가중치와 음의 가중치를 모두 허용하는 가중치 최대 컷 문제는 모든 가중치에서 부호를 뒤집음으로써 가중치 최소 컷 문제로 3차적으로 변환할 수 있다.

하한

Edwards는^[1][2] n개의 꼭지점과 m개의 모서리가 있는 그래프 G에서 다음 두 개의 Max-Cut 하한을 구했습니다(a) G는 임의이지만 (b) G는 연결되어 있습니다).

($a{\displaystyle \frac{}{}}$) ${\displaystyle \frac{\mathrm{m2}}{}}$+ ${\displaystyle 1\frac{4}{}}$ (${\displaystyle \sqrt{2}}$m + ${\displaystyle \sqrt{\frac{1}{}}}$2 - ${\displaystyle 1\frac{4}{}}$ $){$ $displaystyle${\$frac { m}$ + {\frac {1} {$4}}$ \$flac rt${$$2 m + { \ $frac {1}${2}} : - {\ $frac$ {1$}$ ${4}$ \ right$$}

($b{\displaystyle \frac{}{}}$) ${\displaystyle \frac{\mathrm{m2}}{}}$+${\displaystyle \frac{}{\mathrm{}}}$. { $displaystyle${$frac${$m$} {2} + { \$frac$ { n$$- 1 } { 4 }$$。$}$

바인드(b)는 Erd가 추측한 대로 Edwards-Erd's^[3] bound라고 불리는 경우가 많습니다.에드워즈는 확률론적 방법을 사용하여 에드워즈-Erd's bound를 증명했다. Crowston ^[4]등은 선형 대수와 의사-부울 함수 분석을 사용하여 bound를 증명했다.

Crowston 등의 증명을 통해 서명 그래프 G = (V, E, s), 즉 각 가장자리가 + 또는 –로 할당된 그래프에서 균형 하위 그래프 문제(BSP)에^[4] 결합된 Edwards-Erd's를 확장할 수 있다.V를 부분 집합 U 및 W로 분할하는 경우, s(xy) = + 및 x와 y가 동일한 부분 집합에 있거나 s(xy) = – 및 x와 y가 서로 다른 부분 집합이면 가장자리 xy가 균형을 이룹니다.BSP는 G에서 밸런스 에지의 최대수 b(G)를 가지는 파티션을 찾는 것을 목적으로 합니다.Edwards-Erd's는 연결된 모든 서명된 그래프에 대해 b(G)의 하한을 부여한다. (a)는 삼각형이 없는 그래프, 주어진 최대도의 그래프, H가 없는 그래프 등 특수 클래스의 그래프에 대해 개선되었다. 예를 들어,^[5][6][7]

폴작과 투르직은^[8] 에드워즈-에르데스를 가중치 Max-Cut으로 연장했다.

${\displaystyle {\frac {w(G)}{2}}+{\frac {w(T_{min})}{4}},$

여기서 w(G)와 w(T_min)는 G와 그 최소 무게 스패닝트리_min T의 무게입니다최근 Gutin과^[9] Yeo는 임의 가중 그래프에 대한 폴작-터지크 경계를 확장하는 가중 최대-컷에 대한 하한을 다수 얻었다.

계산의 복잡성

최대 컷과 관련된 다음과 같은 의사결정 문제는 이론 컴퓨터 과학에서 광범위하게 연구되어 왔습니다.

그래프 G와 정수 k가 주어졌을 때 G에 k 이상의 크기의 절단이 있는지 여부를 판단한다.

이 문제는 NP-complete로 알려져 있습니다.문제가 NP에 있음을 쉽게 알 수 있습니다.예스 답변은 충분히 큰 컷을 제시하면 쉽게 증명할 수 있습니다.문제의 NP 완전성은 예를 들어 최대 2-만족도(^[10]최대 만족도 문제의 제한)에서 감소함으로써 나타낼 수 있다.결정 문제의 가중 버전은 Karp의 21개의 NP-완전 문제 ^[11]중 하나였습니다. Karp는 분할 문제에서 감소함으로써 NP-완전성을 나타냈습니다.

위의 결정 문제의 표준 최적화 변형은 보통 Maximum-Cut Problem 또는 Max-Cut으로 알려져 있으며 다음과 같이 정의됩니다.

그래프 G가 주어지면 최대 절단을 구한다.

최적화 배리언트는 NP-Hard로 알려져 있습니다.반대로 최소 컷을 찾는 문제는 Ford-Fulkerson 알고리즘을 통해 효율적으로 해결할 수 있는 것으로 알려져 있습니다.

알고리즘

다항식 시간 알고리즘

Max-Cut 문제는 NP-hard이므로 일반 그래프에서 Max-Cut에 대한 다항식 시간 알고리즘은 알려져 있지 않습니다.

평면 그래프

단, 평면 그래프에서 Maximum-Cut Problem은 루트 검사 문제(그래프 G의 최대 컷 세트에 속하지 않는 에지는 듀얼 그라 검사 투어에서 2배되는 에지의 듀얼이라는 의미)와 중복됩니다.ph of G.최적 검사 둘러보기는 평면을 두 개의 부분 집합(곡선의 권선 번호가 짝수인 점의 부분 집합과 권선 번호가 홀수인 부분 집합)으로 구분하는 자체 교차 곡선을 형성합니다. 이 두 부분 집합은 둘러보기에서 홀수 횟수로 나타나는 모든 모서리를 포함하는 절단을 형성합니다.경로 검사 문제는 다항식 시간으로 해결할 수 있으며, 이 이중성을 통해 평면 ^[12]그래프에 대한 다항식 시간 내에 최대 컷 문제를 해결할 수 있습니다.단, Maximum-Bisection 문제는 NP-hard로 ^[13]알려져 있습니다.

근사 알고리즘

Max-Cut 문제는 APX-hard이며,^[14] 이는 P = NP가 아닌 한 최적 솔루션에 임의로 가까운 다항식 시간 근사 체계(PTAS)가 없음을 의미한다.따라서, 알려진 모든 다항식 시간 근사 알고리즘은 엄밀하게 1보다 작은 근사 비율을 달성합니다.

간단한 무작위 0.5 근사 알고리즘이 있습니다. 각 정점에 대해 ^[15][16]동전을 던져 할당해야 할 파티션의 절반을 결정합니다.예상대로 가장자리의 절반은 절단 가장자리입니다.이 알고리즘은 조건부 확률의 방법으로 디랜도밍할 수 있습니다.따라서 간단한 결정론적 다항식-시간 0.5-근사 알고리즘도 있습니다.^[17][18]이러한 알고리즘 중 하나는 주어진 $그래프{\displaystyle }$ G $=$ ( $,$의 정점의 임의의 분할에서 시작하여 $분할$의 한 쪽에서 다른 쪽으로 한 번에 한 정점을 반복 이동함으로써 이러한 유형의 개선이 불가능할 때까지 각 단계에서 솔루션을 개선한다.반복 횟수는 ${\displaystyle 최대}$E(\$displaystyle$ E$$})입니다$$. 이 알고리즘은 각 단계에서 절단을 최소 1개씩 개선하기 때문입니다.알고리즘이 종료되면 모든 정점에 입사하는 에지의 적어도 절반이 절단에 속합니다. 그렇지 않으면 정점을 이동하면 절단이 개선되기 때문입니다.따라서 절단에는 최소${\displaystyle E}$ / ${\displaystyle 2\mathrm{}}$ ${\displaystyle$E /2$}$의 가장자리가 포함됩니다.

가장 잘 알려진 근사 비율을 가진 Max-Cut에 대한 다항식 시간 근사 알고리즘은 근사 $비율{\displaystyle }$ α${\displaystyle 0}$0.${\displaystyle 878}$ ${\displaystyle ,}$\$displaystyle \alpha \apprough$0.$878,}$을 달성하는 반무한 프로그래밍 및 랜덤 반올림을 사용하는 Goemans와 Williamson의 방법이다.

${\displaystyle \alpha = pi }}\min _{0\leq \theta \leq \pi }{\frac {1-\cos \theta }}.}$^[19][20]

고유 게임 추측이 참일 경우 최대 ^[21]컷을 위한 최선의 근사비가 된다.이러한 입증되지 않은 전제 조건 없이 16 $0$0$.$^[22][23]$나은$ 근사 비율로 최대 컷 값을 근사하는 것은 $NP-hard$인 것으로 $입증되었습니다.$

에서는 오픈 소스 구현을 포함한 이 문제에 대한 10가지 휴리스틱에 대한 확장 분석이 있습니다.

매개 변수화된 알고리즘 및 커널화

최소 (파라미터) k 크기의 컷을 찾는 문제가 고정 파라미터 추적가능(FPT)임을 증명하는 것은 간단한 일이지만 그래프 G에 적어도 Edwards-Erd†의 하한 크기 컷이 있는지 여부를 판단하는 문제에 대해서는 고정 파라미터 추적가능성을 나타내는 것은 훨씬 어렵다(파라미터 위의 하한 참조).Crowston 등은 ^[25]이 문제를 $시간{\displaystyle {\mathrm{}}^{}}$ $(n 4)$ 내에$$ 해결할 수 있음을 증명했으며, 크기 $(k 5)$의 커널을 허용합니다. Crowston 등$.$^[25]고정 파라미터 추적성 결과를 균형 서브그래프 문제(BSP, 위의 하한 참조)로 확장하고 커널 크기를 O${\displaystyle ({k\mathrm{}}^{}}$ 3$)\displaystyle$ O$(k^{3})($BSP에도 유지됨)로 개선했습니다.Etscheid와 Mnich는 BSP에 대한 고정 매개변수 추적성 결과를 ${\displaystyle {}^{}}$O${\displaystyle (}$m$)$로, 커널 크기 결과는 O$)$ {$displaystyle$$$O$(k)}$$개$의 정점으로 $개선$했다.

적용들

이론 물리학

통계물리학 및 무질서 시스템에서 Max Cut 문제는 스핀글라스 모델(가장 단순하게 이징 모델)^[27]의 해밀턴을 최소화하는 것과 동일합니다.그래프 G의 이징 모형과 오직 가장 가까운 이웃 상호작용의 경우, 해밀토니안은 다음과 같다.

${\displaystyle H[s]=-\sum_{ij\in E(G)}J_{ij}s_{i}s_{j}}$

여기서 그래프의 각 정점 i는 스핀 값 ${\displaystyle s_{}}$ $=$ ±${\displaystyle 1}$.$${\$displaystyle s_{i$}=\$pm$ 1$.}$ 스핀$$ 구성 파티션${\displaystyle }$V$G)$를 $스핀업{\displaystyle {}^{}}$V +(\$displaystyle$ V$^+})$와 $스핀다운{\displaystyle {}^{}}$ V$(\displaystyle$ V^{+})로 $분할$할 수 있는 스핀 사이트입니다$.$${\displaystyle \S }$ ($V$+ $)({displaystyle \delta$ (V$$$^{+}))$ ${\displaystyle {}^{}}$ 세트를 연결하는 에지 ${\displaystyle \mathrm{세트}}$입니다.그러면 해밀턴을 다음과 같이 다시 쓸 수 있습니다.

$디스플레이 스타일H[s]&=-\sum_{ij\in E(V^{+})}J_{ij}-\sum_{ij\in E(V^{-})}J_{ij}+\sum_{ij\in\delta(V^{+})}J_{ij}\&=-\sum_{ij\in E(G)}J_{ij}+2\sum_{ij\in\delta(V^{+})}J_{ij}\&=C+2\sum _{ij\in\sum (V^{+})}J_{ij}\end{aligned}}$

이 에너지를 최소화하는 것은 최소 컷 문제와 같거나 그래프 가중치를 ${\displaystyle {\mathrm{wi}}_{}}$ j $=$ - ${\displaystyle {\mathrm{Ji}}_{}}$ j$,$ {$displaystyle w_{ij$}=-$J_{ij}$로 설정하여 최대 컷 문제와 동일합니다.^[27]

회로 설계

최대 컷 문제는 VLSI ^[27]설계에 적용되어 있습니다.

「 」를 참조해 주세요.

• 최소 컷
• 최소 k컷
• 홀수 주기 횡단, 최대 초당 유도 하위 그래프를 요청하는 것과 같다.
• 비우호 파티션, 무한 그래프에 대한 관련

메모들

레퍼런스

• 를 클릭합니다Alon, N.; Krivelevich, M.; Sudakov, B. (2005), "Maxcut in H-free graphs", Combin. Probab. Comput., 14: 629–647, doi:10.1017/S0963548305007017, S2CID 123485000.
• 를 클릭합니다Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer.

최대 컷(최적화 버전)은 부록 B(399페이지)의 문제 ND14입니다.

• 를 클릭합니다Bylka, S.; Idzik, A.; Tuza, I. (1999), "Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erd6s inequality", Discrete Math., 194: 39–58, doi:10.1016/S0012-365X(98)00115-0.
• 를 클릭합니다Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Kim, E. J.; Rosamond, F.; Ruzsa, I. Z.; Thomassé, S.; Yeo, A. (2014), "Satisfying more than half of a system of linear equations over GF(2): A multivariate approach", J. Comput. Syst. Sci., 80 (4): 687–696, doi:10.1016/j.jcss.2013.10.002.
• 를 클릭합니다Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G. (2013), "Maximum balanced subgraph problem parameterized above lower bound", Theor. Comput. Sci., 513: 53–64, doi:10.1016/j.tcs.2013.10.026.
• 를 클릭합니다Crowston, R.; Jones, M.; Mnich, M. (2015), "Max-cut parameterized above the Edwards–Erdős bound", Algorithmica, 72 (3): 734–757, doi:10.1007/s00453-014-9870-z, S2CID 14973734.
• 를 클릭합니다Dunning, Iain; Gupta, Swati; Silberholz, John (2018), "What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO", INFORMS Journal on Computing, 30 (3): 608–624, doi:10.1287/ijoc.2017.0798, S2CID 485706.
• 를 클릭합니다Edwards, C. S. (1973), "Some extremal properties of bipartite subgraphs", Can. J. Math., 25 (3): 475–485, doi:10.4153/CJM-1973-048-x, S2CID 121925638.
• 를 클릭합니다Edwards, C. S. (1975), "An improved lower bound for the number of edges in a largest bipartite subgraph", Recent Advances in Graph Theory, pp. 167–181.
• 를 클릭합니다Etscheid, M.; Mnich, M. (2018), "Linear Kernels and Linear-Time Algorithms for Finding Large Cuts", Algorithmica, 80 (9): 2574–2615, doi:10.1007/s00453-017-0388-z, S2CID 16301072.
• 를 클릭합니다Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5.

최대 컷(결정 버전)은 부록 A2.2의 문제 ND16입니다.

최대 초당 서브그래프(결정 버전)는 부록 A1.2의 문제 GT25입니다.

• 를 클릭합니다Gaur, Daya Ram; Krishnamurti, Ramesh (2007), "LP rounding and extensions", in Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
• 를 클릭합니다Goemans, Michel X.; Williamson, David P. (1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM, 42 (6): 1115–1145, doi:10.1145/227683.227684, S2CID 15794408.
• 를 클릭합니다Gutin, G.; Yeo, A. (2021), "Lower Bounds for Maximum Weighted Cut", arXiv:2104.05536 [math.CO].
• 를 클릭합니다Hadlock, F. (1975), "Finding a Maximum Cut of a Planar Graph in Polynomial Time", SIAM J. Comput., 4 (3): 221–225, doi:10.1137/0204019.
• 를 클릭합니다Håstad, Johan (2001), "Some optimal inapproximability results", Journal of the ACM, 48 (4): 798–859, doi:10.1145/502090.502098, S2CID 5120748.
• 를 클릭합니다Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005), "Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs", SIAM Journal on Computing, 35 (1): 110–119, CiteSeerX 10.1.1.62.5082, doi:10.1137/s009753970139567x.
• 를 클릭합니다Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W. (eds.), Complexity of Computer Computation, Plenum Press, pp. 85–103.
• 를 클릭합니다Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?", SIAM Journal on Computing, 37 (1): 319–357, doi:10.1137/S0097539705447372.
• 를 클릭합니다Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), "Greedy methods", in Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
• 를 클릭합니다Mitzenmacher, Michael; Upfal, Eli (2005), Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge.
• 를 클릭합니다Motwani, Rajeev; Raghavan, Prabhakar (1995), Randomized Algorithms, Cambridge.
• 를 클릭합니다Newman, Alantha (2008), "Max cut", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms, Springer, pp. 489–492, doi:10.1007/978-0-387-30162-4_219, ISBN 978-0-387-30770-1.
• 를 클릭합니다Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), "Optimization, approximation, and complexity classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X.
• 를 클릭합니다Poljak, S.; Turzik, Z. (1986), "A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound", Discrete Math., 58 (1): 99–104, doi:10.1016/0012-365X(86)90192-5.
• 를 클릭합니다Scott, A. (2005), "Judicious partitions and related problems", Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 327: 95–117.
• 를 클릭합니다Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), "Gadgets, Approximation, and Linear Programming", Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626.
• 를 클릭합니다Zeng, Q.; Hou, J. (2017), "Bipartite Subgraphs of H-free Graphs", Bull. Aust. Math. Soc., 30 (3): 1–13, doi:10.1017/S0004972716001295.

외부 링크

• "NP 최적화 문제의 개요"에서 "Pierluigi Crescenzi, Viggo Kann, Magnus Haldorsson, Marrek Karpinski, Gerhard Woeginger(2000)", "Maximum Cut"을 참조하십시오.
• Andrea Casini, Nicola Rebagliati(2012), "Max Cut을 해결하기 위한 Python 라이브러리"