| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
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 | Abstract: | We 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 |
|
|
No review found.
Did you like this article?
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
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |