Taglio massimo
# 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.

## Notes

* ↑ Garey-Johnson, 1979.
* ↑ Karp, 1972.
* ↑ Hadlock, 1975.
* ↑ Papadimitriou-Yannakakis, 1991, prova della MaxSNP-completezza.
* ↑ Mitzenmacher-Upfal, 2005, sez. 6.2.
* ↑ Motwani-Raghavan, 1995, sez. 5.1.
* ↑ Mitzenmacher-Upfal, 2005, sez. 6.3.
* ↑ Khuller-Raghavachari-Young, 2007.
* ↑ Newman, 2008.
