NP-hardness conjecture for the bicolored MST crossing number
NP-hardness conjecture for the bicolored MST crossing number
Let be a finite point set in the plane, and let denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding is NP-hard.
This concerns the computational complexity of the bicolored MST crossing number. The paper presents NP-hardness as a conjecture and gives no proof or resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Todor Antić, Morteza Saghafian, Maria Saumell, Felix Schröder, Josef Tkadlec and Pavel Valtr, “How many times can two minimum spanning trees cross?”, arXiv:2601.20060 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.