Sparse graphs and an augmentation problem

• 成果类型: Article
• 署名作者: Kiraly, Csaba; Mihalyko, Andras
• 署名单位: Eotvos Lorand University; HUN-REN
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01689-0
• 发表日期: 2022
• 页码: 119-148
• 关键词: generic global rigidity; percolation; algorithms; frameworks

摘要

For two integers k > 0 and l, a graph G = (V, E) is called (k, l)-tight if vertical bar E vertical bar = k vertical bar V vertical bar-l and i(G)(X) <= k vertical bar X vertical bar-l for each X subset of V for which i(G)(X) >= 1, where i(G)(X) denotes the number of induced edges by X. G is called (k, l)-redundant if G - e has a spanning (k, l)-tight subgraph for all e is an element of E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)-tight spanning subgraph, find a graph H = (V, F) with the minimum number of edges, such that G. H is (k, l)-redundant. We give a polynomial algorithm and a min-max theorem for this augmentation problem when the input is (k, l)-tight. For general inputs, we give a polynomial algorithm when k >= l and show the NP-hardness of the problem when k < l. Since (k, l)-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.