TR-2019-14

Sparse graphs and an augmentation problem (A revised version is available as TR-2020-06)

Csaba Király, András Mihálykó



Abstract

For two integers $k>0$ and $\ell$, a graph $G=(V,E)$ is called $(k,\ell)$-tight if $|E|=k|V|-\ell$ and $|E(X)|\leq k|X|-\ell$ for all $X\sbse V$ for which $k|X|-\ell\geq 0$. $G$ is called $(k,\ell)$-redundant if $G-e$ has a spanning $(k,\ell)$-tight subgraph for all $e\in E$. We consider the following augmentation problem. Given a graph $G=(V,E)$ that has a $(k,\ell)$-tight spanning subgraph, find a graph $H=(V,F)$ with minimum number of edges, such that $G+H$ is $(k,\ell)$-redundant.
 
In this paper, we give a polynomial algorithm and a min-max theorem for this augmentation problem when the input is $(k,\ell)$-tight. For general inputs, we give a polynomial algorithm when $k\geq\ell$ and show the NP-hardness of the problem when $k<\ell$. Since $(k,\ell)$-tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of rigid frameworks redundantly rigid by adding a smallest set of new bars.


Bibtex entry:

@techreport{egres-19-14,
AUTHOR = {Kir{\'a}ly, Csaba and Mih{\'a}lyk{\'o}, Andr{\'a}s},
TITLE = {Sparse graphs and an augmentation problem (A revised version is available as TR-2020-06)},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-14}
}


Last modification: 6.4.2021. Please email your comments to Tamás Király!