Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs (Q1322019)

Consider the following decision problem which P. Winkler and V. Bulitko (independently) showed was undecidable: Given a finite set \(\Phi\) of rooted graphs, and a positive integer \(r\), is there a graph \(G\) such that \(\Phi\) represents, up to isomorphism, the set of all \(r\)-neighborhoods of \(G\)? We show the undecidability of the related problem in which \(G\) is required to be the covering digraph of a partial ordering. Our construction shows that the problem remains undecidable (for certain fixed \(r\)) even when \(G\) is also required to be connected, planar, and bipartite.