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]

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $$k$$-clique, and $$k$$-clan. The concept of $$k$$- club is one of them. A $$k$$-club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $$k$$. It is a relaxation of a clique, which induces a subgraph of diameter $$1$$. We conducted algorithmic studies on finding a $$k$$-club of size as large as possible. In this paper, we show that one can find a $$k$$-club of maximum size in $$O^{*}(1.62^n)$$ time where $$n$$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $$k$$-club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called $$k$$-DN which, under deletion of vertices from a graph, maintains for a given vertex $$v$$ the set of vertices at distances at most $$k$$. From the experimental results that we obtained, we concluded that a $$k$$-club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $$k$$-clubs of maximum size in most of experimental instances. The gap between the size of a $$k$$-club of maximum size and a $$k$$-club found by IDROP is a constant for the number of vertices that we are able to test. [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]