Search

Consider a graph G with vertex set V(G) and edge set E(G). A subset D of V(G) is said to be a dominating set of G if every vertex not in D is adjacent to at least one vertex in D. If, in addition, every vertex not in a dominating set R of G is adjacent to at least one vertex in V (G) - R , then R is called a restrained dominating set of G. A paired restraint dominating set S of a graph G is a restrained dominating set of G satisfying that the induced subgraph by S contains a perfect matching. The problems of computing the dominating set, restrained dominating set, and paired restraint dominating set with minimum cardinality are referred to as the domination, restrained domination, and paired restraint domination problems, respectively. The paired restraint domination problem and its applications are first proposed here. Our focus is on examining the complexity of the proposed problem on extended supergrid graphs and their subclasses, which include grid, diagonal supergrid, and (original) supergrid graphs. The domination problem is known to be NP-complete on grid graphs and, therefore, also on extended supergrid graphs. Our previous research demonstrated that the domination and restrained domination problems on diagonal and original supergrid graphs are NP-complete. However, the complexity of the paired restraint domination problem on grid, diagonal supergrid, and original supergrid graphs remains unknown. The NP-completeness of the paired restraint domination problem on diagonal supergrid graphs is demonstrated in this paper, and this finding is also applicable to the original supergrid graphs and planar graphs with maximum degree 4. We then examine a subclass of diagonal and original supergrid graphs known as rectangular supergrid graphs. These graphs are distinguished by a rectangular shape consisting of m rows and n columns of vertices. Specifically, we address the paired restraint domination problem on R m × n and develop a linear time algorithm for 3 ⩾ m ⩾ 1 and n ⩾ m . Then, when n ⩾ m ⩾ 4 , we obtain a tight upper bound on the minimum size of the paired restraint dominating set of R m × n and then use this upper bound to establish one lower bound. [ABSTRACT FROM AUTHOR]

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]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

Let G = (V , E , w) be a Δ β -metric graph with a distance function w (⋅ , ⋅) on V such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β ⋅ (w (u , x) + w (x , v)) for all u , v , x ∈ V. Given a positive integer p , let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H , vertices (non-hubs) in V ∖ C form an independent set in H , and each non-hub v ∈ V ∖ C is adjacent to exactly one hub in C. Define d H (u , v) = w (u , f (u)) + w (f (u) , f (v)) + w (v , f (v)) where f (u) and f (v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w (u , f (u)) = 0. Let r (H) = ∑ u , v ∈ V d H (u , v) be the routing cost of H. The Single Allocation at most p -Hub Center Routing problem is to find a spanning subgraph H of G such that r (H) is minimized. In this paper, we show that the Single Allocation at most p -Hub Center Routing problem is NP-hard in Δ β -metric graphs for any β > 1 / 2. Moreover, we give 2 β -approximation algorithms running in time O (n 2) for any β > 1 / 2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω (β) , and we examine the structure of any potential o (β) -approximation algorithm. [ABSTRACT FROM AUTHOR]

Abstract A bounded-degree-1 set S in an undirected graph G = (V , E) is a vertex subset such that the maximum degree of G [ S ] is at most one. Given a graph G , the Maximum Bounded-Degree-1Set (Max 1-bds) problem is to find a bounded-degree-1 set S of maximum size in G.A notion related to bounded-degree sets is that of an s - plex used to define the cohesiveness of subgraphs in social networks. An s -plex S in a graph G = (V , E) is a vertex subset such that for each v ∈ S , deg G [ S ] (v) ≥ | S | − s. One can easily show that a graph G has a2-plex of size k iff the complement graph of G has a bounded-degree-1 set of size k. Both the Maximum 2-Plex problem and the Maximum Bounded-Degree-1 Set problem are NP-hard. We give a simple branch-and-reduce algorithm running in polynomial space and applying branching strategies with at most three branches for Max 1-bds. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O ∗ (1. 461 3 n) which is faster than previous exact algorithms. Moreover, we show that the Max 1-bds problem cannot be approximated to a ratio greater than n ϵ − 1 in polynomial time for all ϵ > 0 unless P = NP. Some moderately exponential time approximation algorithms are given for Max 1-bds and its dual problem. [ABSTRACT FROM AUTHOR]

Given a metric graph G = (V , E , w) , a specific vertex c ∈ V , and an integer p , let T be a depth-2 spanning tree of G rooted at c such that c is adjacent to p vertices called hubs and each of the remaining vertices is adjacent to a hub. The Star p -Hub Routing Cost Problem is to find a spanning tree T of G satisfying the conditions stated above such that the sum of distances between all pairs of vertices in T is minimized. In this paper, we prove that the Star p -Hub Routing Cost Problem is NP-hard. A 3-approximation algorithm running in time O (n 2) is given for solving the same problem where n is the number of vertices in the input graph. Moreover, we give an example to show that the analysis of the approximation ratio cannot be better than 2 − ϵ for any ϵ > 0. [ABSTRACT FROM AUTHOR]

A complete weighted graph G = ( V , E , w ) is called Δ β -metric, for some β ≥ 1 / 2 , if G satisfies the β -triangle inequality, i.e., w ( u , v ) ≤ β ⋅ ( w ( u , x ) + w ( x , v ) ) for all vertices u , v , x ∈ V . Given a Δ β -metric graph G = ( V , E , w ) and a center c ∈ V , and an integer p , the Δ β -Star p -Hub Center problem ( Δ β -S p HCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -S p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate the Δ β -S p HCP to a ratio g ( β ) − ϵ is NP-hard and give r ( β ) -approximation algorithms for the same problem where g ( β ) and r ( β ) are functions of β . A subclass of metric graphs is identified that Δ β -S p HCP is polynomial-time solvable. Moreover, some r ( β ) -approximation algorithms given in this paper meet approximation lower bounds. [ABSTRACT FROM AUTHOR]