2022/08/18 by Yuefang Sun, Sun, Yuefang
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2208.08618
openalex publication_date 2022/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the complexity of two types of digraph packing problems: perfect out-forests problem and Steiner cycle packing problem. For the perfect out-forest problem, we prove that it is NP-hard to decide whether a given strong digraph contains a 1-perfect out-forest. However, when restricted to a semicomplete digraph D, the problem of deciding whether D contains an i-perfect out-forest becomes polynomial-time solvable, where i∈ \0,1\. We also prove that it is NP-hard to find a 0-perfect out-forest of maximum size in a connected acyclic digraph, and it is NP-hard to find a 1-perfect out-forest of maximum size in a connected digraph. For the Steiner cycle packing problem, when both k≥ 2, ℓ≥ 1 are fixed integers, we show that the problem of deciding whether there are at least ℓ internally disjoint directed S-Steiner cycles in an Eulerian digraph D is NP-complete, where S⊆ V(D) and |S|=k. However, when we consider the class of symmetric digraphs, the problem becomes polynomial-time solvable. We also show that the problem of deciding whether there are at least ℓ arc-disjoint directed S-Steiner cycles in a given digraph D is NP-complete, where S⊆ V(D) and |S|=k.