Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.09568 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910299979776000 |
|---|---|
| author | Jordán, Tibor Villányi, Soma |
| author_facet | Jordán, Tibor Villányi, Soma |
| contents | Given a graph $G$, a cost function on the non-edges of $G$, and an integer $d$, the problem of finding a cheapest globally rigid supergraph of $G$ in $\mathbb{R}^d$ is NP-hard for $d\geq 1$. For this problem, which is a common generalization of several well-studied graph augmentation problems, no approximation algorithm has previously been known for $d\geq 2$. Our main algorithmic result is a 5-approximation algorithm in the $d=2$ case. We achieve this by proving numerous new structural results on rigid graphs and globally linked vertex pairs. In particular, we show that every rigid graph in $\mathbb{R}^2$ has a tree-like structure, which conveys all the information regarding its globally rigid augmentations. Our results also yield a new, simple solution to the minimum cardinality version (where the cost function is uniform) for rigid input graphs, a problem which is known to be solvable in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09568 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Globally linked pairs and cheapest globally rigid supergraphs Jordán, Tibor Villányi, Soma Combinatorics Given a graph $G$, a cost function on the non-edges of $G$, and an integer $d$, the problem of finding a cheapest globally rigid supergraph of $G$ in $\mathbb{R}^d$ is NP-hard for $d\geq 1$. For this problem, which is a common generalization of several well-studied graph augmentation problems, no approximation algorithm has previously been known for $d\geq 2$. Our main algorithmic result is a 5-approximation algorithm in the $d=2$ case. We achieve this by proving numerous new structural results on rigid graphs and globally linked vertex pairs. In particular, we show that every rigid graph in $\mathbb{R}^2$ has a tree-like structure, which conveys all the information regarding its globally rigid augmentations. Our results also yield a new, simple solution to the minimum cardinality version (where the cost function is uniform) for rigid input graphs, a problem which is known to be solvable in polynomial time. |
| title | Globally linked pairs and cheapest globally rigid supergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.09568 |