Capitolo 1
Il problema dei cammini bilanciati in reti acicliche
1.1 Formulazione
Sia G = (V, E) una rete orientata e aciclica con #V = n e #E = m. Sotto queste ipotesi G ha una struttura a livelli che è possibile mettere in evidenza rinumerando i suoi nodi in accordo ad un ordinamento topologico. Sia h il numero di livelli di G e sia
V =V1UV2U U... Vh una partizione dell’insieme dei nodi tale che
( )
,i j E∀ ∈ ∃ p q, ∈
{
1, 2,...,h}
tali che i V∈ , p j V∈ e p < q. qAd ogni arco
( )
,i j ∈E è associato un costo intero e non negativo che indichiamo conil simbolo . Siano dati inoltre k nodi sorgente cij
{
s s1, ,...,2 sk}
e k nodi destinazione{
t t1, ,...,2 tk}
con . Il problema dei cammini bilanciati su G è il problema diindivi-duare k cammini che connettano le k sorgenti e le k destinazioni date minimizzando la differenza in costo tra il cammino più costoso e quello meno costoso. Ogni sorgente può essere connessa a una qualsiasi destinazione e nessun nodo sorgente o destinazione può rimanere escluso.
2 k ≥
Senza perdere di generalità si può assumere che i nodi sorgente appartengano a e che i nodi destinazione appartengano a . Inoltre, ci si può ricondurre ad una formulazione del problema che fa uso di un unico nodo sorgente e di un unico nodo destinazione nel seguente modo: inseriamo in V due nuovi nodi s e t e in E i 2k archi di costo zero
1
V
h
V
( )
s s, ie per i = 1, 2, …, k. In tal modo s e t appartengono a due livelli fittizi di G che indichiamo con e , rispettivamente. Il problema dei cammini bilanciati può ora essere formulato in maniera equivalente come il problema di individuare k cammini da s a t, che coinvolgano tutti gli archi del tipo
(
t ti,)
0
V Vh+1
bilanciati, tali cioè che sia minimizzata la differenza in costo tra il cammino più costoso e quello meno costoso.
Nelle varianti arc-disjoint e node-disjoint del problema si richiede anche che i k cammi-ni non abbiano, rispettivamente, alcun arco e alcun nodo in comune.
Un’ulteriore variante del problema è quella in cui vengono date k coppie di nodi origi-ne-destinazione,
(
s t1 1,)
,(
s t2, 2)
, … ,(
s tk, k)
, e i k cammini bilanciati da individuaredevono connettere ogni origine con la rispettiva destinazione.
1.2 Complessità computazionale in tempo
In questa sezione si fa ricorso al Subset Sum problem [9] per mostrare che il problema dei cammini bilanciati in reti acicliche è NP-arduo. In un’istanza del Subset Sum pro-blem, dato un intero positivo C e q coefficienti interi positivi , i = 1, …, q, si deve stabilire se esiste un sottoinsieme di tali coefficienti la cui somma è esattamente C. In [9] è dimostrato che il Subset Sum problem è NP-completo.
i
a
Teorema 1.1 ( [6] ) Il problema dei cammini bilanciati in reti acicliche è NP-arduo. Dim. Per semplicità nella dimostrazione si considera il caso k = 2. La dimostrazione viene effettuata mostrando come il Subset Sum problem si riduce polinomialmente alla versione decisionale del problema dei cammini bilanciati. Il problema dei cammini bi-lanciati, nella sua versione decisionale, generalizza il seguente problema: data una rete pesata aciclica G, esistono due cammini il cui costo è esattamente C, per un dato intero positivo C? Data un’istanza del Subset Sum problem, si costruisce una rete con h = q+2 livelli: il livello contiene due nodi sorgente e , il livello contiene due nodi destinazione e . In ogni livello intermedio , 1 < i < h, viene inserito un unico no-do 1 V s1 s2 Vh 1 t t2 Vi i
x , corrispondente al coefficiente (i-1)-esimo ai−1. L’insieme degli archi è definito come segue:
{
(
x xi, j)
|i< j i, =2,...,q}
U
{
(
x ti, 1)
|i=2,...,q+ U1}
{
(
s t2, 2)
}
e i costi degli archi sono: 1 1 i s x i c =a− per i=2,...,q+ 1 cx xi j =aj−1 per i< j i, =2,...,q 1 0 i x t c = per i=2,...,q+ 1 cs t2 2 = C
Ci si riporta infine al caso di un’unica sorgente e un’unica destinazione, aggiungendo i due nodi s e t e i quattro archi di costo zero
(
s s, 1)
,(
s s, 2)
,( )
t t1, e . La rete a li-velli ottenuta è mostrata nella figura sottostante (Figura 1).(
t t2,)
2 i x 2 x xq+1 1 t 2 t 2 s 1 s s t 0 0 0 0 0 0 0 C 1 a q a q a 1 i a− 1 i a− 1 V V2 i V 1 h V− h V Figura 1Bisogna ora mostrare che il Subset Sum problem ha soluzione se e solo se nella rete a livelli costruita esistono due cammini da s a t che connettono s1 e a e s2 t1 t ,
rispetti-vamente, e il cui costo sia esattamente C. Supponiamo che esista un sottoinsieme dei coefficienti ai la cui somma è esattamente C e sia
{
}
1, 2,..., p | per
i i i j l
a a a i <i j< tale l sottoinsieme. Vale quindi
1 j p i j a C = =
∑
. Allora i cammini 1 2 1 ( , ,1 i 1, i 1,..., ip 1 1, , ) P = s s x + x + x + t te P2 =( , , , )s s t t2 2 hanno entrambi costo C.
Viceversa, se esistono due cammini di costo C che connettono
rispettivamente, uno dei due, sia esso , deve necessariamente contenere gli archi
. è dunque un cammino del tipo con
1 e P P2 2
)
1 e a e 2 1 s s t t 1 P(
s s, 1) (
e t t1, P1 ( , ,s s x1 i1+1,xi2+1,...,xip+1 1, , )t t{
1,...,}
per 1,..., ji ∈ q j= p, e quindi la somma dei coefficienti
1, 2,..., p
i i i
a a a è
esattamen-te C. □ Il Subset Sum problem dunque ha soluzione se e solo se il problema dei cammini bilan-ciati da s a t ad esso associato restituisce zero come valore ottimo della funzione obiet-tivo.
1.3 Un algoritmo pseudopolinomiale
Nella descrizione dell’algoritmo si fa riferimento alla formulazione del problema con un’unica sorgente s, connessa alle k sorgenti del livello , e con un’unica destina-zione t, connessa ai nodi destinadestina-zione del livello .
i
s V1
i
t Vh
1.3.1 Descrizione
Sia U il costo (oppure una stima per eccesso del costo) del cammino più costoso di G. Si costruisca una nuova rete GU =
(
VU,EU)
, detta rete espansa, nel seguente modo:{
, ,...,1}
U k V = s s s U{
ip,p=0,1,..., |U i V∈ \ , ,...,{
s s1 sk}
}
{
(
p, p cij)
| ( , ) ,}
U ij E = i j + i j ∈E p≤ −U c .In sono state inserite U copie di ogni nodo i di G: la p-esima copia di i rappre-senta il nodo i in quanto raggiungibile dalla sorgente s in G attraverso un cammino di
U
costo esattamente p. Ad ogni cammino da s a t di costo p in G corrisponde quindi un cammino orientato da s a in p .
t GU
La rete è una rete a livelli la cui dimensione è pseudopolinomiale nella dimensione della rete di input G; infatti ha
U
G
U
G Ο(nU ) nodi e (mU )Ο archi.
Una volta costruita la rete GU, si effettua una ricerca binaria nell’intervallo
[
0,U]
e, per ogni valore intero δ∈[
0,U]
, si eseguono le seguenti operazioni:• si costruisce la famiglia di sottografi di contenente tutti i cammini di che vanno da s ai nodi in
U
G GU
{
p,..., p}
t t +δ per ogni intero p U≤ − ; δ
• si verifica se almeno uno dei sottografi costruiti contiene k cammini distinti. Più precisamente, si verifica se almeno uno dei sottografi contiene k cammini distin-ti da s a desdistin-tinazioni appartenendistin-ti all’insieme
{
p,..., p}
t t +δ , in cui sono coinvolti gli archi
(
s s, i)
∀ ∈i{
1, 2,...,k}
.L’ultimo insieme di cammini restituito è un insieme ottimo di cammini e il corrispon-dente δ è il valore ottimo della funzione obiettivo, cioè la minima differenza in costo tra i cammini.
Dato δ∈
[
0,U]
e un sottografo di GU contenente i cammini di GU da s ai nodi in{
p,..., p}
t t +δ , per verificare se il sottografo in esame contiene k cammini distinti si pro-cede con i seguenti cinque passi:
1. i nodi
{
p,..., p}
t t +δ vengono fusi in un unico nodo, sia esso t%;
2. ∀ =i 1, 2,...,k si fondono in un unico nodo t% tutte le copie del nodo destinazione i originale appartenenti al sottografo; ti
3. si connettono i nuovi nodi tramite gli archi
( )
t t%%i, per 1,2,...,i= k;4. si assegna capacità unitaria agli archi uscenti da s e agli archi ; ai restanti archi invece si assegna una capacità arbitrariamente alta;
(
t t%%i,)
Se il valore del flusso massimo è uguale a k, allora in G esistono k cammini distinti la cui differenza in costo tra il più costoso e quello meno costoso è al più δ . Se invece il valore del flusso massimo è minore di k per ogni sottografo contenente cammini la cui distanza in costo è al più δ , allora la differenza in costo di ogni insieme di k cammini distinti è maggiore di δ . In entrambi i casi l’algoritmo procede con il successivo valore di δ come stabilito dalla ricerca binaria.
1.3.2 Complessità computazionale in tempo dell’algoritmo
Effettuando una ricerca binaria nell’intervallo
[
0,U]
, l’algoritmo controlla (log )Ο U valori di δ . Per ogni valore δ considerato, si calcola il valore del flusso massimo inreti che hanno archi. Poiché il valore del flusso massimo è al più k, que-sto può essere calcolato in tempo
( )U
Ο Ο(mU)
) (kmU
Ο tempo in ogni sottografo. La complessità in tempo dell’intero algoritmo è quindi ( 2log .
kmU U
Ο )
)
1.4 Le varianti arc-disjoint e node-disjoint
Consideriamo ora le varianti arc-disjoint e node-disjoint del problema dei cammini bi-lanciati. Tali versioni sono NP-ardue in senso forte. Nel seguito mostreremo come la richiesta che i cammini siano node-disjoint può essere trasformata, in tempo polinomia-le, in una equivalente richiesta di cammini arc-disjoint e viceversa. Nel seguito verrà quindi analizzato esplicitamente solo il caso node-disjoint; i risultati ottenuti potranno essere poi applicati al caso arc-disjoint tramite la riduzione polinomiale sotto riportata.
1.4.1 Equivalenza delle varianti node-disjoint e arc-disjoint
Sia G = (V, E) il grafo di input su cui è formulato il problema dei cammini bilanciati node-disjoint. Per formulare un problema equivalente, in cui però si richiede che i cam-mini bilanciati siano arc-disjoint anziché node-disjoint, si costruisce un grafo
nel seguente modo:
(
' ', '{ }
1 2 ' , i V V i ∈ =U
i( )
{
1 2}
{
(
2 1)
( )
}
' , | , | , E = i i i V∈ U i j i j ∈E = 2 dove ∀ ∈i V ci i1 2 =0 e ∀( )
i j, ∈E ci j2 1 cij.In Figura 2 è mostrata la trasformazione effettuata localmente ad un nodo.
Figura 2 1
i
i
si trasforma in 1 c 1 c 2 c 2 c 3 c 3 c 4 c 4 c 5 c 5 c 0 2i
Se è un cammino orientato in G, il corrispondente cammino in è . E’ immediato verificare che due cammini in G sono node-disjoint se e solo se i corrispondenti cammini in G sono arc-disjoint.
1 2 ( , ,..., )l P= i i i G' 1 2 1 2 1 2 1 1 2 2 ' ( , , , ,..., , )l l P = i i i i i i P1 e P 1' e '2 P P '
La riduzione in tempo polinomiale dal caso arc-disjoint a quello node-disjoint si ottiene come descritto in [12] costruendo il line graph (definito in [10]) associato al grafo di in-put G. Più precisamente, il line graph orientato L G
( ) (
= V E', ')
di un grafo orientato Gè così definito:
( )
{
}
' u| , v V = x u v ∈E(
)
( )
( )
{
}
' u, v | , e , v l E = x x u v ∈E v l ∈E . In Figura 3 è mostrato un esempio di costruzione di line graph.1 4 3 2 1 2 x x42 3 2 x 1 3 x x34 Figura 3 G L(G)
Sia G = (V, E) il grafo di input su cui è formulato il problema dei cammini bilanciati arc-disjoint. Come primo passo della trasformazione si aggiungono a G due archi
( ) (
s s, e ,t t)
di costo 0 . Si costruisce ora il line graph associato a G denotando coni nodi corrispondenti agli archi
' e '
s t
( ) ( )
s s, e ,t t , rispettivamente, e assegnandoco-sto 0 a tutti gli archi. A queco-sto punto, si sdoppia ogni vertice del line graph in due copie e e si crea un arco
u v
w=x
1
w w2
(
w w1, 2)
assegnandogli un costo pari a , inmo-do che tutti gli archi entranti in (uscenti da) sono ora entranti in (uscenti da ). Il grafo costruito è aciclico e in esso ci sono k cammini node-disjoint da se e solo se in G ci sono k corrispondenti cammini arc-disjoint da . L’intera
trasforma-zione può essere effettuata in tempo
uv c w w1 w2 ' G s' a 't a s t
( )
mΟ . Algoritmi e risultati computazionali ottenu-ti per il caso node-disjoint possono quindi essere applicaottenu-ti anche al caso arc-disjoint so-stituendo Ο
( )
n con Ο( )
m nelle valutazioni della complessità in tempo.1.4.2 Complessità computazionale in tempo
Teorema 1.2 Il problema dei cammini bilanciati node-disjoint è NP-arduo in senso for-te.
Dim. La dimostrazione si effettua per riduzione dal problema 3-Dimensional Matching (3DM). In 3DM sono date q triple <i,j,p> di interi compresi compresi tra 1 e k, e si cer-cano k di queste triple in modo tale che, per ogni intero r∈
[ ]
1,k , tra esse ci siaesatta-mente una tripla <i,j,p> con i r= , esattamente una con j r= ed esattamente una con p= . r
Data dunque un’istanza di 3DM, si costruisce una rete con un nodo sorgente s, un nodo destinazione t e tre livelli intermedi in cui i nodi rappresentano gli interi tra 1 e k, siano essi V1=
{
u1,...,uk}
, V2 ={
v1,...,vk}
e V3 ={
w1,...,wk}
. L’insieme degli archi è invece ilseguente:
E=
{
( )
s t,}
U
{
( )
s u, j | j=1,...,k}
U{
( )
w tj, | j=1,...,k}
U(
,) (
, ,)
|, , è l' esima tripla tra quelle date in input
i j j p u v v w i j p r ⎧ ⎫ ⎪ ⎪ ⎨ ⎬ < > − ⎪ ⎪ ⎩ ⎭
I costi degli archi sono:
cst = + q 1 0 j su c = per j=1,...,k 0 j w t c = per j=1,...,k i j u v c =r e 1 j p v w
c = − +q r con <i j p, , > r-esima tripla di input In Figura 4 è mostrata la rete così ottenuta.
E’ semplice vedere che, oltre al cammino composto dal singolo arco
(
, c’è una cor-rispondenza biunivoca tra i cammini da s a t di costo q+1 e le triple di 3DM. Si può concludere quindi che ci sono k+1 cammini node-disjoint da s a t, ognuno di costo q+1,)
,se e solo se c’è una soluzione ammissibile per l’istanza di 3DM in esame. Si noti che, se tali cammini esistono, ad essi è associato un valore ottimo della funzione obiettivo pari a zero. □
Corollario 1.1 Il problema dei cammini bilanciati node-disjoint in una rete a livelli con un numero costante di livelli è anch’esso NP-arduo in senso forte.
Teorema 1.3 Il problema dei cammini bilanciati arc-disjoint è NP-arduo in senso for-te.
Corollario 1.2 Il problema dei cammini bilanciati arc-disjoint in una rete a livelli con un numero costante di livelli è NP-arduo in senso forte.
Figura 4 1
u
iu
ku
1v
jv
kv
1w
pw
kw
s
t
1 q r− + r 1 q+ 1V
V
2V
3 0 0 0 0 0 01.4.3 Il caso node-disjoint: numero di livelli costante
Si consideri ora il caso in cui il numero di livelli h della rete aciclica di input sia costan-te. Una situazione del genere si presenta nel campo del trasporto, in cui bisogna asse-gnare ai membri di un equipaggio i turni di lavoro in un orizzonte temporale di h gior-ni. In questi casi valori tipici di h sono 5 o 6 per i turni settimanali e 30 per i turni men-sili.
Come visto nel paragrafo precedente, il problema dei cammini bilanciati node-disjoint con un numero di livelli costante è NP-arduo in senso forte. Tuttavia, quando k è
, l’algoritmo pseudopolinomiale descritto in 1.3 può essere adattato per risol-vere anche la variante node-disjoint del problema. Nell’algoritmo che verrà ora descritto si fa uso del metodo color-coding per il calcolo di cammini semplici, ovvero senza ri-petizioni di nodi, descritto in [1]. Come definito in [1], dato un grafo G e una colorazio-ne random dei suoi vertici, un cammino in G si dice colorful se tutti i nodi del cammino sono colorati con colori distinti. Chiaramente un cammino colorful in G è semplice. In [1] viene poi descritto un algoritmo che, dato un grafo
(
log n Ο)
(
,)
G= V E e una colorazione{
}
: 1,...,r V → l dei vertici di G con colori, determina un cammino colorful di
lun-ghezza al più (se ne esiste uno) con una complessità in tempo pari a
l
1
l− 2Ο( )l ⋅|E| nel
caso pessimo.
Prima di procedere con la descrizione dell’algoritmo, si osservi che ogni soluzione am-missibile del problema contiene al più hk nodi, cioè Ο
(
hlogn)
nodi, e che quindi ilproblema può essere formulato come il problema di individuare nodi che formino cammini da s a t che siano bilanciati e node-disjoint.
(
hlogn Ο)
)
n(
log k = Ο1.4.3.1 Descrizione dell’ algoritmo
Data una colorazione random r dei vertici di G effettuata con esattamente hk colori,
{
}
: 1,...,
r V → hk , si estende la definizione di cammino colorful ad un insieme di k
cammini da s a t in G dicendo che tale insieme è colorful se i nodi toccati dai k cammini sono colorati con colori distinti rispetto ad r.
Come primo passo, si effettua un’estensione della colorazione r ai nodi di : tutte le copie (
U
G
p
i p=1,...,U ) di uno stesso nodo i vengono colorate con lo stesso colore di i , cioè r i
( )
.Si applica ora una variante dell’algoritmo descritto in 1.3.1 in cui, per ogni sottografo di generato durante la ricerca binaria in
U
G
[
0,U]
, si cercano k cammini node-disjoint das a t e si usa la colorazione r per assicurarsi che i cammini calcolati non abbiano nodi in comune. Prima di dare una descrizione più accurata di questo passo dell’algoritmo, si osservi che un insieme colorful di k cammini può essere trasformato in un unico cam-mino semplice da s a t colorful effettuando una semplice modifica del sottografo su cui i k cammini vengono cercati: si aggiungono gli archi
( )
t s%i, j ,∀i j =1,...,k, e si cerca un cammino semplice da s a t%contenente k-1 di questi nuovi archi. La ricerca dell’insieme colorful di k cammini quindi si effettua assegnando costo 0 agli archi originali e costo 1 ai nuovi archi, e cercando un cammino colorful da s a t%di costo massimo. Un insieme colorful di k cammini esiste se e solo se il costo massimo restituito è uguale a k-1. La ricerca di tale cammino può essere effettuata adattando il metodo proposto in [1] per il calcolo di un cammino semplice di cardinalità fissata in un grafo orientato. Più precisa-mente, si procede come segue: si supponga che per ogni vertice j del sottografo siano già stati trovati i possibili insiemi di colori di cammini colorful di lunghezza l che con-nettono s a j, siano essi 1, 2,..., fjljl jl jl
C C C . Per ogni j e per ogni l vale
(
!)
! ! jl hk f hk hk l ≤ −e ad ognuno di questi sottoinsiemi di colori è associato il costo massimo dei cammini associati a quel sottoinsieme di colori. Per ogni nodo j, si analizza la sua collezione di insiemi di colori controllando, per ogni insieme b e per ogni arco
jl C
( )
j i, , se . Se( )
appartiene o meno a b jl r i C r i( )
∉Cjlb, allora si aggiunge{ }
( )
b jl C U r i allacol-lezione di i corrispondente ai cammini colorful di lunghezza l+1, cioè
( )
{ }
( 1)b
jl i l
C U r i =Cβ+ per qualcheβ. Il sottografo in esame contiene un insieme colorful
almeno una (tra quelle relative ad una opportuna lunghezza l, con ) non vuota e contenente almeno un insieme con costo associato uguale a k-1.
2k+ ≤ ≤1 l hk+1
1.4.3.2 Complessità computazionale in tempo dell’algoritmo
La ricerca di un cammino semplice colorful richiede
(
2kh)
mU
Ο . Poiché h è costante e k è Ο
(
log n)
, Ο(
2khmU) (
è Ο n mUp)
dove p è Ο( )
h . Data una colorazione r deiver-tici di G, come nel caso generale, l’algoritmo effettua una ricerca binaria nell’intervallo
[
0,U]
e controlla quindi Ο(log )U valori di δ . Per ogni valore di δ considerato, si controlla in ( )ΟU reti se esiste un cammino colorful di costo k-1, operazione che ri-chiede . Fissata quindi una colorazione r, l’algoritmo determina un insieme colorful di cammini bilanciati in tempo(
p n mU Ο)
(
p 2log)
n mU U Ο .Come indicato da Alon et al. in [1], esiste una lista di colorazioni di V tale che, per
o-gni sottoinsieme V' di V con #V'≤hk, esiste una colorazione nella lista che assegna
colori distinti ad ogni vertice in . La cardinalità di tale lista è . Quindi, se si applica l’approccio descritto precedentemente per ogni colorazione r di tale lista, si ottiene un algoritmo deterministico che risolve il problema in tempo
. ' V Ο
(
nplogn)
(
p 2log log)
n mU n U Ο1.5 Il caso di coppie origine-destinazioni date
Consideriamo ora la versione del problema in cui sono fornite in input k coppie di nodi origine-destinazione,
(
s t1 1,) (
,..., s tk, k)
, e in cui i k cammini bilanciati che si cercanodevono connettere rispettivamente . Tale versione può essere risolta con l’algoritmo descritto in 1.4.3.1 semplicemente modificando il grafo nel seguente modo:
1 a ,..., 1 k a
s è connesso solo ad s1, è connesso a ti si+1 per ogni i=1,...,k− , e solo la destinazio-1 ne viene connessa alla super-destinazione t. Ad ogni iterazione si cerca un cammino colorful da s a t che includa, in tale ordine, gli archi
k
t