Five split-edge graph decision problems
DefinitionNondetConn_Supplement_decidesGraphPropertycommunication-complexitygraph-propertieslower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Alice and Bob receive disjoint edge sets of an undirected graph on Fin N; equivalently they receive simple graphs , and the input graph is . According to the selected clause, the output says whether this union is bipartite, cycle-free, Eulerian, Hamiltonian, or planar.
Planarity means the existence of a crossing-free drawing by simple arcs in .
Definition code
import Definitions.Def_NondetConn_Supplement_GraphProperty
import Definitions.Def_NondetConn_Supplement_isEulerian
import Definitions.Def_RobertsonSeymour1986_GM5_IsPlanar
set_option autoImplicit false
namespace NondetConn.Supplement
/-- On a split-edge input `(G_A,G_B)`, decide one of the five properties of the union graph.
The communication theorems separately impose `Disjoint G_A G_B`, matching the paper's
edge-partition model. -/
noncomputable def decidesGraphProperty (property : GraphProperty) (N : ℕ)
(GA GB : SimpleGraph (Fin N)) : Bool := by
classical
exact match property with
| .bipartite => decide ((GA ⊔ GB).IsBipartite)
| .cycleFree => decide ((GA ⊔ GB).IsAcyclic)
| .eulerian => decide (isEulerian (GA ⊔ GB))
| .hamiltonian => decide ((GA ⊔ GB).IsHamiltonian)
| .planar => decide (RobertsonSeymour1986.GM5.IsPlanar (GA ⊔ GB))
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), Theorem 6.2, p.21 (PDF p.23), and proof, p.26 (PDF p.28)