Note on the hardness of generalized connectivity

DOI10.1007/S10878-011-9399-XzbMATH Open1261.90078arXiv1005.0488OpenAlexW2019952679MaRDI QIDQ1928526FDOQ1928526

Authors: Shasha Li, Xueliang Li 

Publication date: 3 January 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: Let $G$ be a nontrivial connected graph of order $n$ and let $k$ be an integer with $2leqkleqn$. For a set $S$ of $k$ vertices of $G$, let $kappa(S)$ denote the maximum number $ell$ of edge-disjoint trees $T_1,T_2,\mathrm{...},T_{e}ll$ in $G$ such that $V(T_i)capV(T_j)=S$ for every pair $i,j$ of distinct integers with $1leqi,jleqell$. A collection $T_1,T_2,\mathrm{...},T_{e}ll$ of trees in $G$ with this property is called an internally disjoint set of trees connecting $S$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by $kapp{a}_k(G)$, of $G$ is defined by $kapp{a}_k(G)=$min$kappa(S)$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus $kapp{a}_2(G)=kappa(G)$, where $kappa(G)$ is the connectivity of $G$, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of the generalized connectivity. At first, we obtain that for two fixed positive integers $k_1$ and $k_2$, given a graph $G$ and a $k_1$-subset $S$ of $V(G)$, the problem of deciding whether $G$ contains $k_2$ internally disjoint trees connecting $S$ can be solved by a polynomial-time algorithm. Then, we show that when $k_1$ is a fixed integer of at least 4, but $k_2$ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when $k_2$ is a fixed integer of at least 2, but $k_1$ is not a fixed integer, we show that the problem also becomes NP-complete. Finally we give some open problems.

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

Recommendations

• A solution to a conjecture on the generalized connectivity of graphs
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)
• On tree-connectivity and path-connectivity of graphs
• scientific article; zbMATH DE number 205336
• On minimally 2-connected graphs with generalized connectivity \(\kappa_3=2\)

zbMATH Keywords

complexityNP-completepolynomial-time\(k\)-connectivityinternally disjoint trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Graph minors. XIII: The disjoint paths problem
• Rainbow trees in graphs and generalized connectivity
• The generalized connectivity of complete bipartite graphs.
• The tree connectivity of regular complete bipartite graphs
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)

Cited In (39)

• The generalized 4-connectivity of locally twisted cubes
• On the minimum size of graphs with given generalized connectivity
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• Directed Steiner tree packing and directed tree connectivity
• The generalized 3-connectivity of the Mycielskian of a graph
• Two kinds of generalized connectivity of dual cubes
• The generalized 4-connectivity of pancake graphs
• Internally disjoint trees in the line graph and total graph of the complete bipartite graph
• The generalized 3-connectivity of two kinds of regular networks
• The generalized 3-connectivity of burnt pancake graphs and godan graphs
• Two lower bounds for generalized 3-connectivity of Cartesian product graphs
• The 4-set tree connectivity of \((n, k)\)-star networks
• The reliability analysis based on the generalized connectivity in balanced hypercubes
• The generalized 4-connectivity of hierarchical cubic networks
• Constructing internally disjoint pendant Steiner trees in Cartesian product networks
• A solution to a conjecture on the generalized connectivity of graphs
• On extremal graphs with at most \(\ell\) internally disjoint Steiner trees connecting any \(n-1\) vertices
• On extremal graphs with exactly one Steiner tree connecting any \(k\) vertices
• Connectivity, super connectivity and generalized 3-connectivity of folded divide-and-swap cubes
• Path-connectivity of lexicographic product graphs
• The generalized connectivity of alternating group graphs and \((n, k)\)-star graphs
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• Generalized Connectivity of Graphs
• The generalized 3-connectivity of graph products
• The generalized connectivity of data center networks
• The \(\lambda_3\)-connectivity and \(\kappa_3\)-connectivity of recursive circulants
• The generalized 3-connectivity of star graphs and bubble-sort graphs
• On minimally 2-connected graphs with generalized connectivity \(\kappa_3=2\)
• Graphs with large generalized (edge-)connectivity
• On tree-connectivity and path-connectivity of graphs
• The generalized 4-connectivity of burnt pancake graphs
• Title not available (Why is that?)
• The generalized connectivity of bubble-sort star graphs
• Reliability assessment of the divide-and-swap cube in terms of generalized connectivity
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Generalized connectivity of some total graphs
• The generalized 4-connectivity of exchanged hypercubes
• The generalized \(3\)-connectivity of exchanged crossed cube
• A result on the 3-generalized connectivity of a graph and its line graph

This page was built for publication: Note on the hardness of generalized connectivity

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