Packing e Covering

ALBERTO CAPRARA, ALESSANDRO PANCONESI, ROMEO RIZZI,
Packing triangles in planar graphs,
ready for submission
descrizione: Dato un grafo planare, vogliamo trovare in esso il massimo numero di triangoli disgiunti. A seconda che li si voglia solamente disgiunti sui nodi od anche sugli archi abbiamo due distinti problemi. Tuttavia, in una trattazione assai unificata, diamo dei PTAS per entrambi i problemi avvalendoci del teorema separatore. Un PTAS é un algoritmo approssimante a qual si voglia precisione ed é in pratica il meglio che si possa sperare quando il problema in questione risulti essere NP-hard. In effetti noi si dimostra inoltre che entrambi i problemi sono NP-hard. Precedentemente solamente il caso di triangoli disgiunti sui nodi era noto essere tale e la dimostrazione basava su una ben piú complessa riduzione che non quella da noi proposta.

ALBERTO CAPRARA, ALESSANDRO PANCONESI, ROMEO RIZZI,
Packing Cuts in Graphs,
in preparation
descrizione: Diamo svariati risultati di inapprossimabilitá per il problema di trovare il maggior numero possibile di tagli disgiunti in un dato grafo. La questione dell' NP-hardness del problema era stata recentemente posta al centro dell'attenzione da alcuni lavori di Ajeev, ma segue ora come conseguenza di questi ben piú forti risultati. (Non approssimabilitá entro un fattore $\log n$ nel caso generale ed APX-hardness in svariati casi particolari). Diamo altresí degli algoritmi approssimati che mostrano come tali risultati siano stretti.

RICHARD C. BREWSTER, PAVOL HELL, SARAH H. PANTEL, ROMEO RIZZI, ANDERS YEO,
Packing paths in digraphs,
accepted by Journal of Graph Theory
descrizione: Un matching puó essere considerato come una collezione di copie di K₂disgiunte sui nodi. Una generalizzazione del probema di trovare un matching di massima cardinalitá é pertanto quella di, fissata una famiglia di grafi ${\cal G}$, e dato un certo grafo in input G, trovare una collezione di sottografi di G disgiunti sui nodi, tutti isomorfi a qualche membro di ${\cal G}$. Questo problema, noto come il ${\cal G}$-packing problem, ha ricevuto molta attenzione nella letteratura. Tuttavia poco era noto nel caso ${\cal G}$sia una famiglia di grafi diretti, se non che questa cornice fosse piú generale. In questo lavoro si é dato inizio all'esplorazione del caso in cui ${\cal G}$é una famiglia di grafi diretti. In particolare, si é affrontato e completamente caratterizzato il caso in cui ${\cal G}$ é una famiglia di cammini diretti. Il problema di coprire il maggior numero di nodi di G é risolvibile in tempo polinomiale se ${\cal G}$ é riducibile o alla famiglia ${\cal G}=\{\vec{P}_1\}$o alla famiglia ${\cal G}=\{\vec{P}_1,\vec{P}_2\}$. In tutti gli altri casi il problema risulta essere $N\!P$-completo.

ROMEO RIZZI, ANDR´AS SEBSO,
A note on Matroid Flows,
in preparation
descrizione: Il lavoro comincia con l'osservare come una per altro importante congettura di Seymour riguardante una certa classe di matroidi fosse di fatto mal posta. Infatti, ove la congettura fosse presa un po' troppo alla lettera, diamo un controesempio alla stessa. Forniamo quindi la versione rivista della congettura e ne esploriamo le relazioni con altre congetture e risultati.

ROMEO RIZZI,
On packing T-joins,
in preparation
descrizione: Investighiamo il legame tra il problema della fattorizzazione di r-grafi ed il problema dell'impaccamento di T-joins.