Search

In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class Π at all times. We consider only hereditary properties Π , for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed Connected F -Node-Deletion Problem, where all graphs of the family F have to be connected and almost tight lower and upper bounds for the Delayed H -Node-Deletion Problem, where there is one forbidden induced subgraph H that may be connected or not. For the Delayed H -Node-Deletion Problem the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected F -Edge-Deletion Problem, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from F . We give a separate analysis for the Delayed Connected H -Edge-Deletion Problem, which is less general but admits a bound that is easier to compute. [ABSTRACT FROM AUTHOR]

For some β ≥ 1 / 2 , a Δ β -metric graph G = (V , E , w) is a complete edge-weighted graph such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β · (w (u , x) + w (x , v)) for all vertices u , v , x ∈ V . A graph H = (V ′ , E ′) is called a spanning subgraph of G = (V , E) if V ′ = V and E ′ ⊆ E . Given a positive integer p, let H be a spanning subgraph of G satisfying the three conditions: (i) there exists a vertex subset C ⊆ V such that C forms a clique of size p in H; (ii) the set V \ C forms an independent set in H; and (iii) each vertex v ∈ V \ C is adjacent to exactly one vertex in C. The vertices in C are called hubs and the vertices in V \ C are called non-hubs. The Δ β - p -Hub Center Problem ( Δ β - p HCP) is to find a spanning subgraph H of G satisfying all the three conditions such that the diameter of H is minimized. In this paper, we study Δ β - p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate Δ β - p HCP to a ratio g (β) - ϵ is NP-hard and we give r (β) -approximation algorithms for the same problem where g (β) and r (β) are functions of β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For 5 + 5 10 ≤ β ≤ 1 , we show that g (β) = 4 β 2 + 3 β - 1 5 β - 1 and r (β) = min { β + β 2 , 4 β 2 + 5 β + 1 5 β + 1 } . Additionally, for β ≥ 1 , we show that g (β) = β · 4 β - 1 3 β - 1 and r (β) = min { β 2 + 4 β 3 , 2 β } . For β ≥ 2 , the upper bound on the approximation ratio r (β) = 2 β is linear in β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For β ≤ 3 - 3 2 , we show that g (β) = r (β) = 1 , i.e., Δ β - p HCP is polynomial-time solvable. [ABSTRACT FROM AUTHOR]