Directed Steiner tree packing and directed tree connectivity

DOI10.1002/JGT.22858MaRDI QIDQ6093140zbMATH OpenOpenAlexFDO

Authors

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.00849

zbMATH Keywords

directed \(k\)-linkagedirected Steiner tree packingdirected tree connectivityEulerian digraphout-treesemicomplete digraphsymmetric digraph

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: For a digraph $D=(V(D),A(D))$, and a set $SsubseteqV(D)$ with $rinS$ and $|S|geq2$, an $(S,r)$-tree is an out-tree $T$ rooted at $r$ with $SsubseteqV(T)$. Two $(S,r)$-trees $T_1$ and $T_2$ are said to be arc-disjoint if $A(T_1)capA(T_2)=emptyset$. Two arc-disjoint $(S,r)$-trees $T_1$ and $T_2$ are said to be internally disjoint if $V(T_1)capV(T_2)=S$. Let $kapp{a}_{S,r}(D)$ and $lambd{a}_{S,r}(D)$ be the maximum number of internally disjoint and arc-disjoint $(S,r)$-trees in $D$, respectively. The generalized $k$-vertex-strong connectivity of $D$ is defined as ${\displaystyle }$kappa_k(D)= min {kappa_{S,r}(D)mid Ssubset V(D), |S|=k, rin S}.${\displaystyle }$ Similarly, the generalized $k$-arc-strong connectivity of $D$ is defined as ${\displaystyle }$lambda_k(D)= min {lambda_{S,r}(D)mid Ssubset V(D), |S|=k, rin S}.${\displaystyle }$ The generalized $k$-vertex-strong connectivity and generalized $k$-arc-strong connectivity are also called directed tree connectivity which extends the well-established tree connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we completely determine the complexity for both $kapp{a}_{S,r}(D)$ and $lambd{a}_{S,r}(D)$ on general digraphs, symmetric digraphs and Eulerian digraphs. In particular, among our results, we prove and use the NP-completeness of 2-linkage problem restricted to Eulerian digraphs. We also give sharp bounds and characterizations for the two parameters $kapp{a}_k(D)$ and $lambd{a}_k(D)$.

Recommendations

• Extremal results for directed tree connectivity
• Strong subgraph connectivity of digraphs
• Strong subgraph k‐connectivity
• scientific article; zbMATH DE number 7144816
• Packing strong subgraph in digraphs

Cites work

• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• A solution to a conjecture on the generalized connectivity of graphs
• A survey of Nordhaus-Gaddum type relations
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem
• Basic Terminology, Notation and Results
• Digraphs
• Edge-disjoint trees containing some given vertices in a graph
• Generalized Connectivity of Graphs
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Hardness and approximation results for packing Steiner trees
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1321108 (Why is no real title available?)
• Note on the hardness of generalized connectivity
• On the generalized (edge-)connectivity of graphs
• Packing of Steiner trees and \(S\)-connectors in graphs
• Packing Steiner trees
• Pendant tree-connectivity
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)
• Strong subgraph k‐connectivity
• Strong subgraph connectivity of digraphs
• The directed subgraph homeomorphism problem
• The Steiner tree packing problem in VLSI design
• Weak Three-Linking in Eulerian Dgraphs

Cited in

(8)

• Directed cut transversal packing for source-sink connected graphs
• Packing strong subgraph in digraphs
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Directed cycle k-connectivity of complete digraphs and complete regular bipartite digraphs
• The directed pendant-tree 3-connectivity of symmetric compositions
• Compositions of digraphs: a survey
• Degree conditions for disjoint path covers in digraphs
• Perfect out-forest problem and directed Steiner cycle packing problem

This page was built for publication: Directed Steiner tree packing and directed tree connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093140)