ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph with nn vertices, and let k1≥3k_1\geq 3 be fixed. For each k1k_1-subset SS of V(G)V(G), let κ(S)\kappa(S) be the maximum number of internally disjoint trees connecting SS, and define

κk1(G)=min⁡{κ(S):S⊆V(G), ∣S∣=k1}.\kappa_{k_1}(G)=\min\{\kappa(S): S\subseteq V(G),\ |S|=k_1\}.

Let kk be an integer satisfying

2≤k≤n−1.2\leq k\leq n-1.

The generalized-connectivity NP-completeness conjecture. Given GG and kk, deciding whether

κk1(G)≥k\kappa_{k_1}(G)\geq k

is NP-complete. For fixed k1k_1 and fixed kk, the corresponding decision problems are described as polynomial-time solvable, whereas the variable-kk complexity remains unknown, including the case k1=3k_1=3.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.