Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs
type: Item
instance of: scholarly article
title: Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs
zbMATH Open document ID: 0790.03045
author: V. Pereyra
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-06-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 562407
zbMATH Keywords: context-free grammar
zbMATH Keywords: decision problem
zbMATH Keywords: \(r\)-neighborhoods
zbMATH Keywords: undecidability
zbMATH Keywords: covering digraph of a partial ordering
MaRDI profile type: MaRDI publication profile
full work available at URL: jctb.1994.1017
OpenAlex ID: W2038845590
DOI: 10.1006/JCTB.1994.1017
Recommended article: Undecidability of linear inequalities in graph homomorphism densities
Recommended article: The \(k\)-neighbourhood-covering problem on interval graphs
Recommended article: An undecidability result on limits of sparse graphs
Recommended article: On the complexity of cover-incomparability graphs of posets
Recommended article: Q4384512
Recommended article: Complexity results for well‐covered graphs
Recommended article: k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
Recommended article: Neighborhood unions and the cycle cover number of a graph
Recommended article: Q3766875
Recommended article: On the weighted complexity of a regular covering of a graph
description: scientific article; zbMATH DE number 562407