Abstract
We show that there exists a graph $G$ with $\Oh(n)$ nodes, where any forest of $n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant arboricity $k$, the result implies the existence of a graph with $\Oh(n^k)$ nodes that contains all $n$-node graphs as node-induced subgraphs, matching a $\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a $\log_2 n +\Oh(1)$ labeling scheme for adjacency queries in forests.
We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).
We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 : STOC '15 |
Antal sider | 10 |
Forlag | Association for Computing Machinery |
Publikationsdato | 2015 |
Sider | 625-634 |
ISBN (Trykt) | 978-1-4503-3536-2 |
DOI | |
Status | Udgivet - 2015 |
Begivenhed | Annual ACM Symposium on the Theory of Computing 2015 - Portland, USA Varighed: 15 jun. 2015 → 17 jun. 2015 Konferencens nummer: 47 |
Konference
Konference | Annual ACM Symposium on the Theory of Computing 2015 |
---|---|
Nummer | 47 |
Land/Område | USA |
By | Portland |
Periode | 15/06/2015 → 17/06/2015 |