NP-completeness conjecture for generalized k_1-connectivity
Statement
Let be a graph with vertices, and let be fixed. For each -subset of , let be the maximum number of internally disjoint trees connecting , and define
Let be an integer satisfying
The generalized-connectivity NP-completeness conjecture. Given and , deciding whether
is NP-complete. For fixed and fixed , the corresponding decision problems are described as polynomial-time solvable, whereas the variable- complexity remains unknown, including the case .
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.