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.
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.[1] La versione pesata di questo problema decisionale era una dei 21 problemi NP-completi di Karp;[2] Karp mostrò l'NP-completezza tramite una riduzione del problema di partizione.
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.[3]
Esiste un semplice algoritmo randomizzato con approssimazione 0.5: per ogni vertice lanciare una moneta per decidere a quale partizione assegnarlo.[5][6] Il valore atteso degli archi appartenenti al cut-set è . 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.[7][8]
Un taglio è un grafo bipartito. Il problema max-cut equivale a trovare il sottografo bipartito con più archi.
Siano un grafo e un sottografo bipartito di G. Allora esiste una partizione 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 un grafo e X in insieme di archi. Allora è 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.[9] Al problema in oggetto sono applicabili le stesse conclusioni dal punto di vista della complessità computazionale.
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.
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.
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.