This report provides proofs and refinements of some results from our companion paper [1: Packing paths in digraphs, R.C. Brewster, P. Hell, S.H. Pantel, R. Rizzi, A. Yeo, Journal of Graph Theory 2003]. We refer the reader to [1] for a more detailed introduction to notation, background, and motivation. Let $\cal G$ be a fixed set of digraphs. Given a digraph $H$, a $\cal G$-packing in $H$ is a collection $\cal P$ of vertex disjoint subgraphs of $H$, not necessarily induced, each isomorphic to a member of $\cal G$. A $\cal G$-packing $\cal P$ is {\em maximum} if the number of vertices belonging to members of $\cal P$ is maximum, over all $\cal G$-packings. The analogous problem for undirected graphs has been extensively studied in the literature. In a companion paper we initiate the study of digraph packing problems, focusing on the case when $\cal G$ is a family of directed paths. We showed that unless $\cal G$ is (essentially) either $\{ \vec{P}_1 \}$, or $\{ \vec{P}_1, \vec{P}_2 \}$, the $\cal G$-packing problem is NP-complete. We use the notation $\vec{P}_k$ for the \emph{directed path of length $k$}, i.e., the path $u_0, u_1, \dots, u_k$ in which all arcs are oriented from $u_{i-1}$ to $u_i$ for $i=1, 2, \dots k$. When ${\cal G} = \{ \vec{P}_1 \}$, the $\cal G$-packing problem is simply the matching problem. In [2: On the complexity of digraph packings, R.C. Brewster, R. Rizzi, IPL 2003], we treat in detail the one remaining case, ${\cal G} = \{ \vec{P}_1, \vec{P}_2 \}$. We give in this case a polynomial time algorithm based on augmenting configurations, and a corresponding Berge-type and Tutte-type theorems. We also give a reduction to bipartite matching. In this report, we give a direct combinatorial algorithm based on augmentations, explore weighted variants of the problem, and give a polyhedral analysis.

Sidepath results on packing $\vec{P}_1$'s and $\vec{P}_2$'s / Brewster, Richard C.; Hell, Pavol; Rizzi, Romeo. - ELETTRONICO. - (2003), pp. 1-13.

Sidepath results on packing $\vec{P}_1$'s and $\vec{P}_2$'s

Rizzi, Romeo
2003-01-01

Abstract

This report provides proofs and refinements of some results from our companion paper [1: Packing paths in digraphs, R.C. Brewster, P. Hell, S.H. Pantel, R. Rizzi, A. Yeo, Journal of Graph Theory 2003]. We refer the reader to [1] for a more detailed introduction to notation, background, and motivation. Let $\cal G$ be a fixed set of digraphs. Given a digraph $H$, a $\cal G$-packing in $H$ is a collection $\cal P$ of vertex disjoint subgraphs of $H$, not necessarily induced, each isomorphic to a member of $\cal G$. A $\cal G$-packing $\cal P$ is {\em maximum} if the number of vertices belonging to members of $\cal P$ is maximum, over all $\cal G$-packings. The analogous problem for undirected graphs has been extensively studied in the literature. In a companion paper we initiate the study of digraph packing problems, focusing on the case when $\cal G$ is a family of directed paths. We showed that unless $\cal G$ is (essentially) either $\{ \vec{P}_1 \}$, or $\{ \vec{P}_1, \vec{P}_2 \}$, the $\cal G$-packing problem is NP-complete. We use the notation $\vec{P}_k$ for the \emph{directed path of length $k$}, i.e., the path $u_0, u_1, \dots, u_k$ in which all arcs are oriented from $u_{i-1}$ to $u_i$ for $i=1, 2, \dots k$. When ${\cal G} = \{ \vec{P}_1 \}$, the $\cal G$-packing problem is simply the matching problem. In [2: On the complexity of digraph packings, R.C. Brewster, R. Rizzi, IPL 2003], we treat in detail the one remaining case, ${\cal G} = \{ \vec{P}_1, \vec{P}_2 \}$. We give in this case a polynomial time algorithm based on augmenting configurations, and a corresponding Berge-type and Tutte-type theorems. We also give a reduction to bipartite matching. In this report, we give a direct combinatorial algorithm based on augmentations, explore weighted variants of the problem, and give a polyhedral analysis.
2003
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Sidepath results on packing $\vec{P}_1$'s and $\vec{P}_2$'s / Brewster, Richard C.; Hell, Pavol; Rizzi, Romeo. - ELETTRONICO. - (2003), pp. 1-13.
Brewster, Richard C.; Hell, Pavol; Rizzi, Romeo
File in questo prodotto:
File Dimensione Formato  
03-008.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 498.41 kB
Formato Adobe PDF
498.41 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358656
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact