Online Graph Embedding in Star Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918506655645696 |
|---|---|
| author | Dallot, Julien Melnyk, Darya Pacut, Maciej Schmid, Stefan |
| author_facet | Dallot, Julien Melnyk, Darya Pacut, Maciej Schmid, Stefan |
| contents | Graph embedding is a fundamental problem of mapping nodes of a guest graph into a host graph while minimizing the distance distortion, with broad applications, including virtual network embeddings into physical topologies, VLSI design, or community detection in social networks. However, in many real-world applications the guest graph changes over time and the embedding can adapt to these changes (e.g. virtual machine migration in network embeddings). Static embeddings are inherently inefficient in comparison to adaptive embeddings, but it remains an unresolved algorithmic challenge to design efficient embedding algorithms that adapt to the demand on-the-fly, i.e., that are online. In this paper, we derive optimal deterministic and randomized online algorithms for the online graph embedding problem in star host graphs. This is an essential building block on the way to design algorithms for more complex host graphs, representing a single node and its neighborhood. We start by presenting a $1.5$-competitive deterministic algorithm and showing that no deterministic algorithm can perform better. Our main contribution is a randomized algorithm that achieves a significantly better competitive ratio of $11/9 \approx 1.222$. Both the deterministic and the randomized algorithms are optimal, which we prove by deriving tight lower bounds for the competitiveness of any algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17051 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Graph Embedding in Star Graphs Dallot, Julien Melnyk, Darya Pacut, Maciej Schmid, Stefan Data Structures and Algorithms Graph embedding is a fundamental problem of mapping nodes of a guest graph into a host graph while minimizing the distance distortion, with broad applications, including virtual network embeddings into physical topologies, VLSI design, or community detection in social networks. However, in many real-world applications the guest graph changes over time and the embedding can adapt to these changes (e.g. virtual machine migration in network embeddings). Static embeddings are inherently inefficient in comparison to adaptive embeddings, but it remains an unresolved algorithmic challenge to design efficient embedding algorithms that adapt to the demand on-the-fly, i.e., that are online. In this paper, we derive optimal deterministic and randomized online algorithms for the online graph embedding problem in star host graphs. This is an essential building block on the way to design algorithms for more complex host graphs, representing a single node and its neighborhood. We start by presenting a $1.5$-competitive deterministic algorithm and showing that no deterministic algorithm can perform better. Our main contribution is a randomized algorithm that achieves a significantly better competitive ratio of $11/9 \approx 1.222$. Both the deterministic and the randomized algorithms are optimal, which we prove by deriving tight lower bounds for the competitiveness of any algorithm. |
| title | Online Graph Embedding in Star Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.17051 |