The monotonicity conjecture for recognizing generating complete bipartite subgraphs
Statement
Let be positive integers with and , and let and . Let be a family of graphs for which recognizing generating subgraphs isomorphic to is NP-complete. Monotonicity conjecture. Then recognizing generating subgraphs of graphs in isomorphic to is NP-complete as well. This conjecture proposes that NP-completeness for recognizing generating subgraphs isomorphic to a smaller complete bipartite graph extends to larger complete bipartite graphs within the same family. The paper establishes the corresponding complexity results for the relevant complete bipartite graphs by minor modifications of an earlier proof, but the stated general implication is presented as a conjecture.
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.