Monotonicity conjecture for computing the Laplacian p-spectral radius
Statement
Let be a graph, and for let denote its Laplacian -spectral radius. Consider the computational problem of finding from the input graph . Computational monotonicity conjecture. If , then finding can be reduced to finding in polynomial time.
The conjecture is motivated by the fact that the cases and have different computational behavior: the former is computable in linear time, whereas the latter is NP-complete. It proposes that increasing does not make the corresponding exact-value problem computationally easier.
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.