NP-hardness conjecture for the bicolored MST crossing number

From papers

Let PP be a finite point set in the plane, and let cr-MST(P)\operatorname{cr-MST}(P) denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding cr-MST(P)\operatorname{cr-MST}(P) 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

No solutions have been posted yet.