Taglio massimo

Un taglio massimo

In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut.

Il problema può essere enunciato semplicemente come segue. Si vuole ottenere un sottinsieme S dell'insieme dei vertici tale che il numero di archi tra S e l'insieme complementare abbia la più alta cardinalità possibile.

Esiste una versione più avanzata del problema, che riguarda i grafi pesati. In questa versione, ad ogni arco è associato un numero reale, detto "peso", e l'obiettivo del problema è di massimizzare non il numero di archi ma il peso totale degli archi fra S ed il suo complemento. Il problema max-cut su grafi pesati è solitamente ristretto ai pesi non-negativi, dato che pesi negativi possono determinare un problema di diversa natura.

Complessità computazionale

Il seguente problema decisionale legato al taglio massimo è stato largamente studiato nell'informatica teorica:

Dato un grafo G ed un intero k, determinare se esiste un taglio di dimensione almeno k in G.

Il problema è noto essere NP-completo. Verificare che il problema è alpiù NP è semplice: ogni soluzione è verificabile in breve tempo, ovvero il tempo necessario a calcolare la cardinalità dello specifico cut-set ed eseguire il confronto con k. Invece, a NP-completezza può essere dimostrata, ad esempio, tramite riduzione da MAX-2-SAT, noto problema NP-difficile. La versione pesata di questo problema decisionale era una dei 21 problemi NP-completi di Karp; Karp mostrò l'NP-completezza tramite una riduzione del problema di partizione.

La variante canonica, posta come problema di ottimizzazione, è definita come:

Dato un grafo G, trovare un taglio massimo.

Algoritmi polinomiali

Il problema max-cut è NP-difficile, dunque non è conosciuto nessun problema che lo risolva in tempo polinomiale su un grafico generico.

Tuttavia, in un grafo planare, il problema risulta duale a quello del postino cinese (il problema di trovare il percorso più breve che visita ogni arco del grafico almeno una volta), nel senso che gli archi che non appartengono al cut-set del taglio massimo di un grafo G sono i corrispettivi degli archi doppiati nella visita ottimale del grafo duale di G. Questa corrispondenza permette di risolvere in tempo polinomiale il problema del taglio massimo su grafi planari.

Algoritmi di approssimazione

Il problema max-cut è APX-hard, ovvero, non esiste uno schema di approssimazione in tempo polinomiale per esso, a meno che P = NP. Dunque, ogni algoritmo di approssimazione raggiunge un rapporto di approssimazione strettamente minore di uno.

Esiste un semplice algoritmo randomizzato con approssimazione 0.5: per ogni vertice lanciare una moneta per decidere a quale partizione assegnarlo. Il valore atteso degli archi appartenenti al cut-set è ${\frac {|E|}{2}}$. Questo algoritmo può essere "derandomizzato" con il metodo delle probabilità condizionate, divenendo un semplice algoritmo deterministico che approssima in tempo polinomiale la soluzione ottimale del problema con indice di approssimazione 0.5.

Sottografo bipartito massimo

Un taglio è un grafo bipartito. Il problema max-cut equivale a trovare il sottografo bipartito con più archi.

Siano $G=(V,E)$ un grafo e $H=(V,X)$ un sottografo bipartito di G. Allora esiste una partizione $(S,T)$ di V tale che ogni arco in X abbia un estremo in S e l'altro in T. In altri termini, esiste un taglio in H tale che l'insieme di taglio contenga X. Quindi esiste un taglio in G tale che l'insieme di taglio sia un sovrainsieme di X.

Al contrario, siano $G=(V,E)$ un grafo e X in insieme di archi. Allora $H=(V,X)$ è un sottografo bipartito di G.

Riepilogando, dato un sottografo bipartito con k archi, esiste un taglio con un cut-set di almeno k archi, e viceversa. Di conseguenza, il problema di trovare un sottografo bipartito massimo è essenzialmente lo stesso problema di trovare un taglio massimo. Al problema in oggetto sono applicabili le stesse conclusioni dal punto di vista della complessità computazionale.

Bibliografia

• Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela e Marco Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003.
• Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
• Daya Ram Gaur e Ramesh Krishnamurti, LP rounding and extensions, in Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, 2007.
• Michel X. Goemans e David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, in Journal of the ACM, vol. 42, n. 6, 1995, pp. 1115–1145, DOI:10.1145/227683.227684.
• F. Hadlock, Finding a Maximum Cut of a Planar Graph in Polynomial Time, in SIAM J. Comput., vol. 4, n. 3, 1975, pp. 221–225, DOI:10.1137/0204019.
• Johan Håstad, Some optimal inapproximability results, in Journal of the ACM, vol. 48, n. 4, 2001, pp. 798–859, DOI:10.1145/502090.502098.
• Klaus Jansen, Marek Karpinski, Andrzej Lingas e Eike Seidel, Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs, in SIAM Journal on Computing, vol. 35, n. 1, 2005, DOI:10.1137/s009753970139567x.
• Richard M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computation, Plenum Press, 1972, pp. 85–103.
• Subhash Khot, Guy Kindler, Elchanan Mossel e Ryan O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, in SIAM Journal on Computing, vol. 37, n. 1, 2007, pp. 319–357, DOI:10.1137/S0097539705447372.
• Samir Khuller, Balaji Raghavachari e Neal E. Young, Greedy methods, in Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, 2007.
• Michael Mitzenmacher e Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge, 2005.
• Rajeev Motwani e Prabhakar Raghavan, Randomized Algorithms, Cambridge, 1995.
• Alantha Newman, Max cut, in Encyclopedia of Algorithms, Springer, 2008, p. 1, DOI:10.1007/978-0-387-30162-4_219, ISBN 978-0-387-30770-1.
• Christos H. Papadimitriou e Mihalis Yannakakis, Optimization, approximation, and complexity classes, in Journal of Computer and System Sciences, vol. 43, n. 3, 1991, pp. 425–440, DOI:10.1016/0022-0000(91)90023-X.
• Luca Trevisan, Gregory Sorkin, Madhu Sudan e David Williamson, Gadgets, Approximation, and Linear Programming, in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 2000, pp. 617–626.
• Francisco Barahona, Martin Grötschel, Michael Jünger e Gerhard Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, in Operations Research, vol. 36, n. 3, 1988, pp. 493–513, DOI:10.1287/opre.36.3.493, JSTOR 170992.

Collegamenti esterni

• (EN) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger, Maximum Cut, in A compendium of NP optimization problems, KTH Royal Institute of Technology, 2000.
• (EN) Andrea Casini, Nicola Rebagliati, A Python library for solving Max Cut, su code.google.com, 2012.