Complexity results in graph reconstruction

DOI10.1016/J.DAM.2006.04.038MaRDI QIDQ867853zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Rahul Tripathi, Lane A. Hemaspaandra, Stanisław P. Radziszowski

Publication date 19 February 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.04.038

graph isomorphism legitimate deck reconstruction numbers

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Complexity results in graph reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q867853)