NP-completeness conjecture for the strong geodetic set problem on complete multipartite graphs
Statement
A strong geodetic set of a graph is a vertex set satisfying the strong geodetic property, and the associated decision problem asks whether a graph has such a set of size at most a prescribed bound. A complete multipartite graph is a graph whose vertex set is partitioned into independent parts with every pair of vertices in distinct parts adjacent.
Strong geodetic set complexity conjecture. The strong geodetic set problem restricted to complete multipartite graphs is NP-complete.
The conjecture is motivated by an analogy with the NP-complete Knapsack problem: selecting parts corresponds approximately to selecting items, with part size acting as weight and the number of pairs within a part as value. The source reports no reduction proving NP-hardness, so the conjecture remains open.
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.