Degree Sequence Reconstruction from Subgraph Traces
Abstract
The goal of degree sequence reconstruction is to recover the ordered vector of degrees of an unknown graph from vertex deleted traces, where each vertex is deleted independently with probability p. We provide two algorithms for reconstruction; the first uses rejection sampling to reduce the problem to an estimation problem for a mixture distribution. Combined with prior trace reconstruction results, this gives a reconstruction algorithm using ExpÕ (n1/3) traces, although no sub-exponential time decoder is known. Our other approach involves recovering certain graph invariants, degree moments, that can identify a graphs degree sequence. Extremal polynomial bounds show that Θ̃(n1/2) degree moments are necessary and sufficient to reconstruct the degree sequence, which leads to an algorithm with ExpÕ(n1/2) trace complexity. The same polynomial machinery yields a sub-exponential time decoder for the degree sequence from the moments. Additionally, we give an O(n3) upper bound and a Ω(n2) lower bound for the trace complexity of recovering the number of edges.
Related
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Degree sequence condition for pancyclicity in tough graphs
- The realization graph of every degree sequence has a Hamilton path
- On the maximally edge-connected square graphs with degree sequence conditions
- P-stable degree sequence regions for bipartite and directed graphs
BibTeX
@misc{gandikota2026degree,
title = {{Degree Sequence Reconstruction from Subgraph Traces}},
author = {Venkata Gandikota and Arick Grootveld and Haodong Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.09397},
eprint = {2609.09397},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09397},
}
RIS
TY - UNPB
TI - Degree Sequence Reconstruction from Subgraph Traces
AU - Venkata Gandikota
AU - Arick Grootveld
AU - Haodong Yang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2609.09397
UR - https://arxiv.org/abs/2609.09397
AB - The goal of degree sequence reconstruction is to recover the ordered vector of degrees of an unknown graph from vertex deleted traces, where each vertex is deleted independently with probability p. We provide two algorithms for reconstruction; the first uses rejection sampling to reduce the problem to an estimation problem for a mixture distribution. Combined with prior trace reconstruction results, this gives a reconstruction algorithm using ExpÕ (n^1/3) traces, although no sub-exponential time decoder is known. Our other approach involves recovering certain graph invariants, degree moments, that can identify a graphs degree sequence. Extremal polynomial bounds show that Θ̃(n^1/2) degree moments are necessary and sufficient to reconstruct the degree sequence, which leads to an algorithm with ExpÕ(n^1/2) trace complexity. The same polynomial machinery yields a sub-exponential time decoder for the degree sequence from the moments. Additionally, we give an O(n^3) upper bound and a Ω(n^2) lower bound for the trace complexity of recovering the number of edges.
ER -