Complexity results in graph reconstruction
type: Item
instance of: scholarly article
title: Complexity results in graph reconstruction
zbMATH Open document ID: 1117.05078
author: Edith Hemaspaandra
author: Rahul Tripathi
author: Lane A. Hemaspaandra
author: Stanisław P. Radziszowski
published in: Discrete Applied Mathematics
publication date: 2007-02-19T00:00:00Z
review text: This paper takes a look at the reconstruction problem mainly from the point of view of space and time complexity, in particular the relative complexity of the graph isomorphism problem and variants of the legitimate deck problem. The authors extend these variants to the situations where \(c\geq1\) vertices or edges are deleted and also where only a subdeck of the full (alleged) deck is given. For example, if LED denotes the problem of determining whether a given set of graphs is the legitimate edge-deck of some graph, then \(k\text{-LED}_c\) denotes the variant in which \(c\) edges are removed and only \(k\) subgraphs from the full deck are given. Various results are given, for example, that the graph isomorphism problem is polynomial-time isomorphic to \(k\text{-LED}_c\). In the last part of the paper the authors consider reconstruction numbers. This is basically the problem of determining how few subgraphs from the deck are required to reconstruct a graph. Strengthening a result of \textit{R. M. Bryant} [J. Comb. Theory 11, 139--141 (1971; Zbl 0196.27402)] they show that, for all \(k\geq2\) and \(n\geq1\), there is a partial deck of \(k\) endvertex-deleted subgraphs on \((2^{k-1}+1)n+k\) vertices with at least \(2^n\) graphs having all of these subgraphs in their deck. This paper is highly recommended to anyone interested in graph reconstruction from the computational point of view.
reviewed by: Josef Lauri
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5128016
zbMATH Keywords: legitimate deck
zbMATH Keywords: graph isomorphism
zbMATH Keywords: reconstruction numbers
MaRDI profile type: Publication
full work available at URL: j.dam.2006.04.038
OpenAlex ID: W1562828531
cites work: New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
cites work: Graph Isomorphism is in SPP
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: On Ulam's conjecture for separable graphs
cites work: Q3975132
cites work: Graph reconstruction—a survey
cites work: Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
cites work: On a conjecture concerning the reconstruction of graphs
cites work: The Multiple Sequence Alignment Problem in Biology
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: Threshold Computation and Cryptographic Security
cites work: Q5544087
cites work: Parallel concepts in graph theory
cites work: The Reconstruction of a Tree from its Maximal Subtrees
cites work: The graph reconstruction number
cites work: On log-tape isomorphisms of complete sets
cites work: The complexity theory companion
cites work: On Reconstructing a Graph
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: A congruence theorem for trees
cites work: Q4273947
cites work: On the complexity of graph reconstruction
cites work: Proof of Harary's conjecture on the reconstruction of trees
cites work: Q4414312
cites work: THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
cites work: Some basic observations on Kelly's conjecture for graphs
cites work: Q3824449
cites work: Q4856614
cites work: Q3483308
cites work: The ally-reconstruction number of a tree with five or more vertices is three
cites work: Q3870936
cites work: Graph reconstruction from subgraphs
cites work: A low and a high hierarchy within NP
cites work: Graph isomorphism is in the low hierarchy
cites work: Q3259049
DOI: 10.1016/J.DAM.2006.04.038
Recommended article: Mathematical Foundations of Computer Science 2004
Recommended article: Q3684156
Recommended article: On the complexity of graph reconstruction
Recommended article: Q4349617
Recommended article: Q3312273
Recommended article: Q3059003
Recommended article: Reconstruction of small graphs and digraphs
Recommended article: On the reconstruction of the matching polynomial and the reconstruction conjecture
Recommended article: The edge reconstruction number of a disconnected graph
Recommended article: Graph reconstruction -- some new developments
description: scientific article; zbMATH DE number 5128016