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
- 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.