• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 19 Feb 2025 (v1), last revised 25 Feb 2026 (this version, v3)] Title:Strong and Hiding Distributed Certification of Bipartiteness View PDF HTML (experimental)Abstract:In this paper, we study the problem of certifying whether a graph is bipartite (i • $2$-colorable) with a locally checkable proof (LCP) that is able to hide a $2$-coloring from the verifier • More precisely, we say an LCP for $2$-coloring is hiding if, in a yes-instance, it is possible to assign certificates to nodes without revealing an explicit $2$-coloring • Motivated by the search for promise-free separations of extensions of the LOCAL model in the context of locally checkable labeling (LCL) problems, we also require the LCPs to satisfy what we refer to as the strong soundness property • This is a strengthening of soundness that requires that, in a no-instance (i • , a non-$2$-colorable graph) and for every certificate assignment, the subset of accepting nodes must induce a $2$-colorable subgraph

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 19 Feb 2025 (v1), last revised 25 Feb 2026 (this version, v3)] Title:Strong and Hiding Distributed Certification of Bipartiteness View PDF HTML (experimental)Abstract:In this paper, we study the problem of certifying whether a graph is bipartite (i.e. $2$-colorable) with a locally checkable proof (LCP) that is able to hide a $2$-coloring from the verifier. More precisely, we say an LCP for $2$-coloring is hiding if, in a yes-instance, it is possible to assign certificates to nodes without revealing an explicit $2$-co

Sources: