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.
References
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).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.