Li's conjecture on the complexity of generalized connectivity
Statement
Let be a graph, let be a -subset of , and let . For a set , write for the maximum number of internally disjoint trees connecting .
Li's conjecture. Given , , and an integer with , deciding whether
is an -complete problem.
The conjecture concerns the unresolved case of the complexity of deciding whether a prescribed set can be connected by many internally disjoint trees. The corresponding problem is polynomial-time solvable when both and are fixed, while it is known to be -complete for fixed ; the case remains open in the source.
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.