Online and Approximate Network Construction from Bounded Connectivity Constraints
Jansson, Jesper LU ; Levcopoulos, Christos LU
and Lingas, Andrzej
LU
(2023)
In International Journal of Foundations of Computer Science
- Abstract
The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V
of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S1,S2,…,Sr⊆V
of connectivity constraints, the objective is to find a set E
of edges such that each Si
induces a connected subgraph of the graph (V,E)
and the total cost of E
is minimized. First, we study the online version where every constraint must be satisfied immediately... (More)
The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V
of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S1,S2,…,Sr⊆V
of connectivity constraints, the objective is to find a set E
of edges such that each Si
induces a connected subgraph of the graph (V,E)
and the total cost of E
is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O(B2log n)-competitive and O((B+log r)-competitive polynomial-time algorithms, where B is an upper bound on the size of constraints, while r,n denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an Ω(B)-competitive lower bound as well as an Ω(√B)-competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an O(√n (log n+log r))
-competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most d
. Among other things, we provide a polynomial-time ((B, 2)−B+2)(B, 2)
-approximation algorithm for the Network Construction problem with the d
-diameter requirements, when each constraint has at most B
vertices, and show the APX-completeness of this variant. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/9366de5b-711e-4ab3-87b0-298dc9fdcced
- author
- Jansson, Jesper
LU
; Levcopoulos, Christos
LU
and Lingas, Andrzej
LU
- organization
- publishing date
- 2023
- type
- Contribution to journal
- publication status
- published
- subject
- in
- International Journal of Foundations of Computer Science
- publisher
- World Scientific Publishing
- external identifiers
-
- scopus:85146304091
- ISSN
- 0129-0541
- DOI
- 10.1142/S0129054122500265
- language
- English
- LU publication?
- yes
- id
- 9366de5b-711e-4ab3-87b0-298dc9fdcced
- date added to LUP
- 2023-01-25 12:36:27
- date last changed
- 2023-02-06 15:10:43
@article{9366de5b-711e-4ab3-87b0-298dc9fdcced,
abstract = {{<br/>The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V<br/> of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S<sub>1</sub>,S<sub>2</sub>,…,S<sub>r</sub>⊆V<br/> of connectivity constraints, the objective is to find a set E<br/> of edges such that each S<sub>i</sub><br/> induces a connected subgraph of the graph (V,E)<br/> and the total cost of E<br/> is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O(B<sup>2</sup>log n)-competitive and O((B+log r)-competitive polynomial-time algorithms, where B is an upper bound on the size of constraints, while r,n denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an Ω(B)-competitive lower bound as well as an Ω(√B)-competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an O(√n (log n+log r))<br/>-competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most d<br/>. Among other things, we provide a polynomial-time ((B, 2)−B+2)(B, 2)<br/>-approximation algorithm for the Network Construction problem with the d<br/>-diameter requirements, when each constraint has at most B<br/> vertices, and show the APX-completeness of this variant.}},
author = {{Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej}},
issn = {{0129-0541}},
language = {{eng}},
publisher = {{World Scientific Publishing}},
series = {{International Journal of Foundations of Computer Science}},
title = {{Online and Approximate Network Construction from Bounded Connectivity Constraints}},
url = {{http://dx.doi.org/10.1142/S0129054122500265}},
doi = {{10.1142/S0129054122500265}},
year = {{2023}},
}