Let be a fixed set of digraphs. Given a digraph H, a -packing in H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . A -packing is maximum if the number of vertices belonging to members of is maximum, over all -packings. The analogous problem for undirected graphs has been extensively studied in the literature. The purpose of this paper is to initiate the study of digraph packing problems. We focus on the case when is a family of directed paths. We show that unless is (essentially) either , or , the G-packing problem is NP-complete. When , the -packing problem is simply the matching problem. We treat in detail the one remaining case, . We give in this case a polynomial algorithm for the packing problem. We also give the following positive results: a Berge type augmenting configuration theorem, a min-max characterization, and a reduction to bipartite matching. These results apply also to packings by the family consisting of all directed paths and cycles. We also explore weighted variants of the problem and include a polyhedral analysis.

Packing paths in digraphs

RIZZI, ROMEO;
2003-01-01

Abstract

Let be a fixed set of digraphs. Given a digraph H, a -packing in H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . A -packing is maximum if the number of vertices belonging to members of is maximum, over all -packings. The analogous problem for undirected graphs has been extensively studied in the literature. The purpose of this paper is to initiate the study of digraph packing problems. We focus on the case when is a family of directed paths. We show that unless is (essentially) either , or , the G-packing problem is NP-complete. When , the -packing problem is simply the matching problem. We treat in detail the one remaining case, . We give in this case a polynomial algorithm for the packing problem. We also give the following positive results: a Berge type augmenting configuration theorem, a min-max characterization, and a reduction to bipartite matching. These results apply also to packings by the family consisting of all directed paths and cycles. We also explore weighted variants of the problem and include a polyhedral analysis.
2003
graph packing; matching; augmenting configuration; min-max theorem; good characterization
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11562/409616
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact