[Algoritmi] Hitting set con conflitti
Salve a tutti, nel risolvere questo esercizio, mi sono trovato davanti ad un lemma da dimostrare che sta alla base dell'algoritmo che ho implementato.
Prima di tutto il problema è il seguente:
Nel problema classico hittingset, un’istanza [tex]H=(U,B_{1},\ldots,B_{m},k)[/tex] consiste di:
(1) insieme universo U di n elementi;
(2) m sottoinsiemi[tex]B_{1},\ldots,B_{m}[/tex] di U ;
(3) intero k .
Un hitting set V per I è un sottoinsieme di U tale che
(1) [tex]|V|\leq k[/tex] ;
(2) per i = 1, . . . , m, [tex]V\cap B_{i}\neq\textrm{Ø}[/tex] ;
In questo progetto studiamo anche una versione di hitting set con conflitti. L’istanza [tex]C=(U,B_{1},\ldotp\ldotp\ldotp,B_{m},(u_{1},v_{1}),\ldots,(u_{f,}v_{f}),k)[/tex] specifica anche una sequenza di coppie [tex](u_{1},v_{1}),\ldots,(u_{f},v_{f})[/tex] di elementi di U che chiamamo i conflitti. Un hitting set con conflitti V per C è un sottoinsieme di U tale che:
1. V è un hitting set per l’istanza [tex]I=(U,B_{1},\ldots,B_{m},k)[/tex]
2. per [tex]i=1,\ldots,f , |V\cap\{u_{i},v_{i}\}|\leq1[/tex] ; cioè per ogni conflitto, V contiene al più uno di [tex]u_{i} e v_{i}[/tex] .
Il lemma dice:
Dato [tex]H=(U,B=\{B_{1},\ldots,B_{m}\},(u_{1},v_{1}),\ldots,(u_{f},v_{f}),k\}[/tex], sia [tex]b_{i}[/tex] un elemento di un qualsiasi sottoinsieme[tex]B_{j}[/tex] di B , allora H ha un hitting set, che rispetta i conflitti, di cardinalità al massimo k se e solo se [tex]H'=(U,B-b_{i},(u_{1},v_{1}),\ldots,(u_{f},v_{f}),k\}[/tex] ha un hitting set, che rispetta i conflitti, di cardinalità al massimo k-1 .
Dove definiamo [tex]B-b_{i}[/tex] come l'insieme di sottoinsiemi di elementi di U , ottenuto a partire da B, eliminando tutti i sottoinsiemi che contengono l'elemento [tex]b_{i}[/tex] .
La dimostrazione che ho dato è la seguente:
Prova: Supponiamo che H abbia un hitting set S di cardinalità al massimo k , che rispetta i conflitti. Allora S deve contenere almeno un elemento per ogni sottoinsieme di B , senza creare conflitti, allora in particolare contiene [tex]b_{i}[/tex] . Di conseguenza l'insieme [tex]S-\{b_{i}\}[/tex] deve coprire tutti i sottoinsiemi presenti in [tex]B-b_{i}[/tex] , perchè altrimenti S non sarebbe stato un hitting set, e quindi [tex]S-\{bi\}[/tex] è un hitting set di cardinalità al massimo k-1 per H' , ed inoltre continua a rispettare i conflitti, perchè ho solo tolto un elemento, che già prima non creava conflitto.
Viceversa supponiamo che H' abbia un hitting set T di cardinalità k-1 , sicuramente T copre tutti i sottoinsiemi presenti in [tex]B-b_{i}[/tex] , con [tex]b_{i}[/tex] tale che, [tex]\forall\: t\in T\:\nexists\:(b_{i},t)[/tex] nelle coppie dei conflitti. Quindi se costruisco l'insieme [tex]T\cup\{b_{i}\}[/tex] , allora T coprirà tutti i sottoinsiemi di U in H , e quindi [tex]T\cup\{b_{i}\}[/tex] è un hitting set per H di cardinalità al massimo k , che continua a rispettare i conflitti.
Però il viceversa della dimostrazione non mi convince pienamente. Sapete darmi qualche consiglio su come correggere eventuali errori?
Prima di tutto il problema è il seguente:
Nel problema classico hittingset, un’istanza [tex]H=(U,B_{1},\ldots,B_{m},k)[/tex] consiste di:
(1) insieme universo U di n elementi;
(2) m sottoinsiemi[tex]B_{1},\ldots,B_{m}[/tex] di U ;
(3) intero k .
Un hitting set V per I è un sottoinsieme di U tale che
(1) [tex]|V|\leq k[/tex] ;
(2) per i = 1, . . . , m, [tex]V\cap B_{i}\neq\textrm{Ø}[/tex] ;
In questo progetto studiamo anche una versione di hitting set con conflitti. L’istanza [tex]C=(U,B_{1},\ldotp\ldotp\ldotp,B_{m},(u_{1},v_{1}),\ldots,(u_{f,}v_{f}),k)[/tex] specifica anche una sequenza di coppie [tex](u_{1},v_{1}),\ldots,(u_{f},v_{f})[/tex] di elementi di U che chiamamo i conflitti. Un hitting set con conflitti V per C è un sottoinsieme di U tale che:
1. V è un hitting set per l’istanza [tex]I=(U,B_{1},\ldots,B_{m},k)[/tex]
2. per [tex]i=1,\ldots,f , |V\cap\{u_{i},v_{i}\}|\leq1[/tex] ; cioè per ogni conflitto, V contiene al più uno di [tex]u_{i} e v_{i}[/tex] .
Il lemma dice:
Dato [tex]H=(U,B=\{B_{1},\ldots,B_{m}\},(u_{1},v_{1}),\ldots,(u_{f},v_{f}),k\}[/tex], sia [tex]b_{i}[/tex] un elemento di un qualsiasi sottoinsieme[tex]B_{j}[/tex] di B , allora H ha un hitting set, che rispetta i conflitti, di cardinalità al massimo k se e solo se [tex]H'=(U,B-b_{i},(u_{1},v_{1}),\ldots,(u_{f},v_{f}),k\}[/tex] ha un hitting set, che rispetta i conflitti, di cardinalità al massimo k-1 .
Dove definiamo [tex]B-b_{i}[/tex] come l'insieme di sottoinsiemi di elementi di U , ottenuto a partire da B, eliminando tutti i sottoinsiemi che contengono l'elemento [tex]b_{i}[/tex] .
La dimostrazione che ho dato è la seguente:
Prova: Supponiamo che H abbia un hitting set S di cardinalità al massimo k , che rispetta i conflitti. Allora S deve contenere almeno un elemento per ogni sottoinsieme di B , senza creare conflitti, allora in particolare contiene [tex]b_{i}[/tex] . Di conseguenza l'insieme [tex]S-\{b_{i}\}[/tex] deve coprire tutti i sottoinsiemi presenti in [tex]B-b_{i}[/tex] , perchè altrimenti S non sarebbe stato un hitting set, e quindi [tex]S-\{bi\}[/tex] è un hitting set di cardinalità al massimo k-1 per H' , ed inoltre continua a rispettare i conflitti, perchè ho solo tolto un elemento, che già prima non creava conflitto.
Viceversa supponiamo che H' abbia un hitting set T di cardinalità k-1 , sicuramente T copre tutti i sottoinsiemi presenti in [tex]B-b_{i}[/tex] , con [tex]b_{i}[/tex] tale che, [tex]\forall\: t\in T\:\nexists\:(b_{i},t)[/tex] nelle coppie dei conflitti. Quindi se costruisco l'insieme [tex]T\cup\{b_{i}\}[/tex] , allora T coprirà tutti i sottoinsiemi di U in H , e quindi [tex]T\cup\{b_{i}\}[/tex] è un hitting set per H di cardinalità al massimo k , che continua a rispettare i conflitti.
Però il viceversa della dimostrazione non mi convince pienamente. Sapete darmi qualche consiglio su come correggere eventuali errori?
Risposte
Non so niente di questo argomento, ma l'implicazione sbagliata mi sembra la prima e non la seconda. In particolare, nella prima implicazione supponi che l'elemento \(b_i\) faccia parte dell'hitting set ma non c'è niente nelle ipotesi o nelle proposizioni precedenti che lo faccia a mio parere supporre. È infatti sicuramente vero che l'hitting set deve contenere almeno un elemento per ogni sottoinsieme \(B_i\) (è nella definizione), ma non è detto che \(b_i\) debba per forza essere uno di questi. Che cosa non ti convince invece della seconda implicazione?
Per completare la prima implicazione si potrebbe forse notare che preso un qualsiasi elemento \(b_i\) e un hitting set \(S\), sostituendo tutti gli elementi di \(S\) che appartengono agli stessi insiemi \(B_j\) a cui appartiene \(b_i\) (questo insieme di punti non è vuoto per la definizione di hitting set) con \(b_i\) si ottiene nuovamente un hitting set e si può quindi supporre che \(b_i\) faccia parte di un qualche hitting set.
Per completare la prima implicazione si potrebbe forse notare che preso un qualsiasi elemento \(b_i\) e un hitting set \(S\), sostituendo tutti gli elementi di \(S\) che appartengono agli stessi insiemi \(B_j\) a cui appartiene \(b_i\) (questo insieme di punti non è vuoto per la definizione di hitting set) con \(b_i\) si ottiene nuovamente un hitting set e si può quindi supporre che \(b_i\) faccia parte di un qualche hitting set.
Ciao, grazie per avermi risposto.
Per quanto riguarda il bi della prima implicazione, forse ho espresso male il concetto, ma il bi è un generico elemento dell'hitting set S, su cui fissiamo la nostra attenzione.
Mentre quello che non mi convince della seconda implicazione è che io devo scegliere il bi per cui esiste l'hitting set senza conflitti di cardinalità k-1 su B-bi. Quindi io per avere l'hitting set di cardinalità k-1 devo prima sver scelto il bi adatto, e questo mi sembra un pò una forzatura, perchè vorrei partire dal B-bi qualunque sia bi e poterlo sempre espandere e ottenere nuovamente un hitting set senza conflitti
Per quanto riguarda il bi della prima implicazione, forse ho espresso male il concetto, ma il bi è un generico elemento dell'hitting set S, su cui fissiamo la nostra attenzione.
Mentre quello che non mi convince della seconda implicazione è che io devo scegliere il bi per cui esiste l'hitting set senza conflitti di cardinalità k-1 su B-bi. Quindi io per avere l'hitting set di cardinalità k-1 devo prima sver scelto il bi adatto, e questo mi sembra un pò una forzatura, perchè vorrei partire dal B-bi qualunque sia bi e poterlo sempre espandere e ottenere nuovamente un hitting set senza conflitti
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo