Two disjoint shortest paths in the equal-hop path construction
Statement
Let be a node that is neither the source nor a virtual source. Let , , , and be the quantities defined in Equations and. Let and be the two colors different from the color of , and suppose that
Two-path conjecture. Node always has two disjoint shortest paths and satisfying one of the following alternatives: (1) runs from through the color- neighbors to , while runs from through the color- neighbors to ; or (2) runs from through the color- neighbors to , while runs from through the color- neighbors to . Here, an -hop path set is a set of paths all having length , so the assertion concerns shortest paths in the colored network construction. The claim is a structural property used to establish the relationship between the network equations and the existence of suitable disjoint paths; its resolution is not specified in the supplied text.
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.