Given a (possibly infinite) family S of oriented stars, an S-packing in a digraph D is a collection of vertex disjoint subgraphs of D, each isomorphic to a member of S. The STACKING problem asks for the maximum number of vertices, of a host digraph D, that can be covered by an S-packing of D. We prove a dichotomy for the decision version of the S-packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problems, we provide Hall type min-max theorems, including versions for (locally) degree-constrained variants of the problems. An oriented star can be specified by a pair of (k, l) is an element of N-2 \ (0, 0) denoting the number of out-and in-neighbours of the centre vertex. For p, q, d is an element of N U {infinity}, we denote by S-p,S-q,S-d the family of stars (k, l) such that k <= p, and l <= q, and 0 < k + l <= d. We prove the S-PACKING problem is polynomial if S = S-p,S-q,S-d for some p, q, d is an element of Z(+) U {infinity}, and NP-complete otherwise.

Oriented star packings

RIZZI, ROMEO
2008-01-01

Abstract

Given a (possibly infinite) family S of oriented stars, an S-packing in a digraph D is a collection of vertex disjoint subgraphs of D, each isomorphic to a member of S. The STACKING problem asks for the maximum number of vertices, of a host digraph D, that can be covered by an S-packing of D. We prove a dichotomy for the decision version of the S-packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problems, we provide Hall type min-max theorems, including versions for (locally) degree-constrained variants of the problems. An oriented star can be specified by a pair of (k, l) is an element of N-2 \ (0, 0) denoting the number of out-and in-neighbours of the centre vertex. For p, q, d is an element of N U {infinity}, we denote by S-p,S-q,S-d the family of stars (k, l) such that k <= p, and l <= q, and 0 < k + l <= d. We prove the S-PACKING problem is polynomial if S = S-p,S-q,S-d for some p, q, d is an element of Z(+) U {infinity}, and NP-complete otherwise.
2008
Oriented stars; Packing problems; Min-max theorems; 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/409547
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact