Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'488'730
Articles rated: 2609

29 March 2024
 
  » arxiv » cs.CC/0410021

 Article overview


Complexity Results in Graph Reconstruction
Edith Hemaspaandra ; Lane A. Hemaspaandra ; Stanislaw P. Radziszowski ; Rahul Tripathi ;
Date 11 Oct 2004
Subject Computational Complexity; Discrete Mathematics ACM-class: F.1.3; F.2.2 | cs.CC cs.DM
AbstractWe investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts $c geq 1$ of deletion: 1) $GI equiv^{l}_{iso} VDC_{c}$, $GI equiv^{l}_{iso} EDC_{c}$, $GI leq^{l}_{m} LVD_c$, and $GI equiv^{p}_{iso} LED_c$. 2) For all $k geq 2$, $GI equiv^{p}_{iso} k-VDC_c$ and $GI equiv^{p}_{iso} k-EDC_c$. 3) For all $k geq 2$, $GI leq^{l}_{m} k-LVD_c$. 4)$GI equiv^{p}_{iso} 2-LVC_c$. 5) For all $k geq 2$, $GI equiv^{p}_{iso} k-LED_c$. For many of these results, even the $c = 1$ case was not previously known. Similar to the definition of reconstruction numbers $vrn_{exists}(G)$ [HP85] and $ern_{exists}(G)$ (see page 120 of [LS03]), we introduce two new graph parameters, $vrn_{forall}(G)$ and $ern_{forall}(G)$, and give an example of a family ${G_n}_{n geq 4}$ of graphs on $n$ vertices for which $vrn_{exists}(G_n) < vrn_{forall}(G_n)$. For every $k geq 2$ and $n geq 1$, we show that there exists a collection of $k$ graphs on $(2^{k-1}+1)n+k$ vertices with $2^{n}$ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.
Source arXiv, cs.CC/0410021
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser claudebot






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica