# A Polynomial Algorithm for Weighted Toughness of Interval Graphs

Authors: Ming Shi; Zongtian Wei
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The concept of toughness, introduced by Chva´tal, has been widely used as an important invulnerability parameter. This parameter is generalized to weighted graphs, and the concept of weighted toughness is proposed. A polynomial algorithm for computing the weighted toughness of interval graphs is given.


---

## Body

## 1. Introduction

The concept of invulnerability was proposed in the early research on the connectivity of communication networks, which reflect the ability of a network to resist deliberate damage from the outside [1]. As a widely used invulnerability parameter, toughness was introduced by Chva´tal in 1973.Definition 1 (see [2]).
LetG be a noncomplete graph. The toughness of G is defined as(1)tG=minXωG−X:X⊂VG,ωG−X≥2.
If there existsX∗⊆VG such that tG=X∗/ωG−X∗, then X∗ is called a t-tough set, denoted as t-set. In particular, for the complete graph Kn, define tKn=∞.
In reality, the vertices of a graph have different roles. Usually, vertex-weighted graphs are used to represent such network models, that is, each vertex is associated with a real number to distinguish such a difference. To measure the invulnerability of networks, we introduce the concept of weighted toughness of graphs.Definition 2.
LetG be a noncomplete vertex-weighted graph. The weighted toughness of G is defined as(2)twG=minwXωG−X:X⊂VG,ωG−X≥2,where w:V⟶R+ is a nonnegative weight function and wX=∑v∈Xwv is the weight of the vertex cut X. For a vertex-weighted complete graph Kn, define twKn=∞.
By the definition, the greater the weighted toughness, the stronger the invulnerability of the vertex-weighted graph.Definition 3.
LetG be a vertex-weighted noncomplete graph. If there exists X∗⊆VG such that twG=wX∗/ωG−X∗, then X∗ is called an achieving cut of G.
When the weights of all vertices are equal, weighted toughness is equivalent to toughness. The problem of toughness computation isNP-hard [3]. However, there exists a polynomial algorithm for toughness computation of interval graphs [4]. The definition of the interval graph is given below.Definition 4 (see [5]).
A graphG is called an interval graph, if ∀v∈VG corresponds to a closed interval Iv=av,bv, and uv∈EG if and only if Iu∩Iv≠∅. We call Ivv∈V the interval representation of G.
Due to the special structure and properties, interval graphs are widely used in theoretical research and engineering practice. For example, the archeology chronological order of unearthed items [6], the scheduling problems in computer science [7], and the determination of biology model of DNA sequences [8]. Many scholars have studied the algorithm and structure of interval graphs. Kratsch et al. gave a polynomial time algorithm for computing scattering numbers and toughness of interval graphs [4]. Broersma et al. gave a linear time algorithm for computing scattering numbers of interval graphs [9]. Li et al. gave a polynomial algorithm for computing weighted scattering number of interval graphs [10].
In this paper, we consider the algorithm of computing weighted toughness of interval graphs. The following work is arranged in two parts. In Section2, some elementary definitions and notations, as well as some preliminary results are given. An algorithm for computing the weighted toughness of interval graphs is given based on the investigation of properties of achieving cuts and local minimum cuts. In Section 3, we summarize our work by the complexity analysis of the algorithm.
This paper only considers the finite simple undirected graphs. For the terminology and notations not defined here, we refer the reader to [11].


## 2. An Algorithm for Computing Weighted Toughness of Interval Graphs

In this section, we firstly investigate the properties of achieving cuts and local minimum cuts of interval graphs. The number of vertex cut of a graph increases with its order exponentially. Fortunately, it is not necessary to consider all vertex cuts when computing the weighted toughness of interval graphs.Definition 5.
(see [12]). Let G be an interval graph and X be a vertex cut. If for every proper subset Y⊂X and ωG−Y<ωG−X, then X is called a strong cut of G.Theorem 1.
LetG be an interval graph with nonnegative weights’ function w:V⟶R+. Then, any achieving cut of G is a strong cut.Proof.
LetX be an achieving cut of G but not a strong cut. By Definition 5, there must exist a vertex u∈X such that ωG−X≤ωG−X−u. Since wX−u<wX,(3)wX−uωG−X−u<wXωG−X=twG.
This contradicts to thatX is an achieving cut of G. The proof is completed.Definition 6 (see [12]).
LetG be an interval graph. Consider a point x such that minibi<x<maxiai. If the end point immediately to the left of x is right end point and the end point immediately to the right of x is a left end point, then Cx is called a minimal local cut of G.
Figure1 is an example of interval graph and its interval representation. The minimal local cuts of G are C4.5=I2,I3, C6.25=I3,I4, C8.75=I4,I6, C12.5=I4,I6, and C16.5=I9,I10.Figure 1
An interval graphG and its interval representation.
(a)(b)Lemma 1 (see [12]).
Any strong cut of an interval graph can be expressed as a union of minimal local cuts.By Theorem1 and Lemma 1, we know that any achieving cut can be expressed as a union of minimal local cuts. Therefore, the weighted toughness of an interval graph can be computing by the unions of minimal local cut. In 2006, Ray et al. presented an algorithm for computing minimal local cuts of an interval graph and proved that the time complexity is On2 [12].Definition 7.
LetCα1,Cα2,…,Cαk be all the minimal local cuts of an interval graph G, where α1<α2<⋯<αk. Then, Cαi and Cαi+1 are called adjacent, i=1,2,…,k−1.Theorem 2.
LetCα1,Cα2,…,Cαk be all the minimal local cuts of a weighted interval graph G. If Cαi and Cαj are disjoint, then(4)minwCαiωG−Cαi,wCαjωG−Cαj≤wCαi∪CαjωG−Cαi∪Cαj.Proof.
SinceCαi∩Cαj=∅, wCαi∪Cαj=wCαi+wCαj. On the contrary, ωG−Cαi∪Cαj≤ωG−Cαi+ωG−Cαj. Without loss of generality, suppose that wCαi/ωG−Cαi≥wCαj/ωG−Cαj. Then,(5)wCαiωG−Cαj−wCαjωG−Cαi≥0.
Therefore,(6)wCαi∪CαjωG−Cαi∪Cαj−wCαjωG−Cαj≥wCαi+wCαjωG−Cαi+ωG−Cαj−wCαjωG−Cαj=wCαiωG−Cαj−wCαjωG−CαiωG−CαjωG−Cαi+ωG−Cαj≥0.
The proof is completed.Remark 1.
The conclusion of Theorem2 is true for the cases where the number of minimal local cuts is greater than 2.Theorem 3.
LetCαi,Cαi+1,Cαi+2 be three sequential adjacent minimal local cuts of an interval graph G. If Cαi∩Cαi+1=∅, then Cαi∩Cαi+2=∅.Proof.
By contradiction, ifCαi∩Cαi+2≠∅, then there exists a vertex v∈Cαi∩Cαi+2. Let u∈Cαi+1, z∈Cαi+2−Cαi, and the interval representation of v,u,z be a,b, ai+1,bi+1, and ai+2,bi+2, respectively.
By the definition of interval representation,a<ai+1<ai+2. Since v∈Cαi+2, bi+1<b, and ai+1,bi+1⊂a,b. Thus, v∈Cαi+1. This contradicts that Cαi∩Cαi+1=∅. The proof is completed.
Theorem 3 shows that, for an interval graph, nonadjacent minimal local are disjoint. The algorithm for finding the union of minimal local cuts with nonempty intersection is given below.Theorem 4.
The time complexity of Algorithm1 is On3Algorithm 1:Union of minimal local cuts with nonempty intersection.
Input: An interval graph G; minimal local cuts Cα1,Cα2,…,Cαk.Output: Union of minimal local cuts with nonempty intersection.(1)
Step 1:j=0;Sj=∅;r=0;Xr=∅;i=1;(2)
Step 2: If i≠k, turn to Step 3, otherwise, stop;(3)
Step 3: If Cαi∩Cαi+1≠∅, turn to Step 4, otherwise, j=0, output Xr, i=i+1, turn to Step 2;(4)
Step 4:j=j+1;(5)
Step 5:Sj=Cαi∪Cαi+1;(6)
Step 6:r=r+1;(7)
Step 7:Xr=Xr−1∪Sj;(8)
Step 8:i=i+1.Proof.
Step 3 needsCαiCαi+1 comparisons to determine whether Cαi∩Cαi+1=∅. Step 5 finds union of two minimal local cuts with nonempty intersection, which need CαiCαi+1 comparisons. Similarly, Step 7 needs Xr−1Sj comparisons. It is easy to know that Step 2 to Step 8 need k−1 circulations, and the total computations does not exceed k−12Cαiαi+1+Xr−1Sj+2. Since an interval graph of order n has at most n−2 minimal local cuts and each minimal local cut contains at most n−2 vertices, the complexity of Algorithm 2 is On3. The proof is completed.
By the discussion above, to computing the weighted toughness of an interval graph, it is sufficient to consider the union of minimally local cuts with nonempty intersection, as well as the number of connected components of the remaining subgraphs.Algorithm 2:Component number corresponding to the union of minimally local cuts with nonempty intersection.
Input: interval graph G, a union of minimally local cuts with nonempty intersection X.Output:ωG−X.(1)
Step 1:ω=0,S0=∅,j=0,i=1.(2)
Step 2: set the vertices in X to ‘visited’, the vertices in V−X to ‘unvisited’, S0=X.(3)
Step 3:G=G−S0.(4)
Step 4: visit the vertices of V−X in order of the vertex subscripts, find the ‘unvisited’ vertex u which has the minimum subscript, and set the vertex ‘visited’.(5)
Step 5:Mj=Mj∪u.(6)
Step 6:Si=Si−1∪Mj.(7)
Step 7: if Mj≠∅, turn to Step 8; otherwise, if V−Si≠∅, ω=ω+1,j=0,i=i+1, return to Step 4 and if V−Si=∅, output ω+1.(8)
Step 8: find a vertex with the largest subscript in Mj, y; if y has an ‘unvisited’ neighbor z, turn to Step 9; otherwise, Mj=Mj−y, return to Step 7.(9)
Step 9: set z to ‘visited’.(10)
Step 10:j=j+1.(11)
Step 11:Mj=Mj−1∪z.(12)
Step 12:i=i+1.(13)
Step 13:Si=Si−1∪z, return to Step 8.Theorem 5.
The time complexity of Algorithm2 is On3.Proof.
The total computations of Step 2 isn. In Step 3, obtaining graph G=G−S0 requires 2VS0 operations. Step 4 requires 1+V−XlogV−X comparisons at most. Step 6 requires Si−1Mj comparisons. Step 7 requires Mj comparisons to determine whether Mj=∅. Similarly, V−Si comparisons are needed to determine whether V−Si=∅. If Mj=∅ and V−Si=∅, then the total computations for Step 4 to Step 7 does not exceed ωV−XlogV−X+2+Si−1Mj+Mj+V−Si+3. If Mj≠∅, finding vertex y with the largest subscript in Mj, MjlogMj comparisons are needed. If y has an ‘unvisited’ neighbor z in V−X, finding the neighbor of y in V−X needs at most n−1 comparisons. The total circulations of Step 9 to Step 13 are V−X−1, so the total computations of Step 8 to Step 13 is V−X−1MjlogMj+n−1. If y does not have ‘unvisited’ neighbors, the computations for Step 7 to Step 8 is Mj. Therefore, the total computations for Step 7 to Step 13 is V−X−1MjlogMj+n−1+Mj. Since Mj≤n−X,Si−1≤n,Si≤n,ω≤n,X≤n−2, the time complexity of algorithm 2 is On3. The proof is completed.
Now, we give an algorithm for computing the weighted toughness and achieving cuts of interval graphs.Example 1.
Use Algorithm3 to compute the weighted toughness of G1 and G2 in Figure 2.
Consider cutsX1=I2,I3, X2=I3,I4, X3=I4,I6, X4=I9,I10, X5=I2,I3,I4, and X6=I3,I4,I6. Let λi=wXi/ωG−Xi, i∈1,2,…,6.
ForG1, λ1=7.00, λ2=7.50, λ3=5,33, λ4=7.00, λ5=12.00, and λ6=5.25. Therefore, twG1=mini∈1,2,…,6λi=λ6=5.25, and the achieving cut is X2∪X3. Similarly, twG2=0.20, and the achieving cut is X3.
This example shows that the value of weighted toughness is not only related to the structure and weights of the graph but also related to the way of weight association.Algorithm 3:Weighted toughness and achieving cuts of interval graphs.
Input: An interval weighted graph G, all minimal local cuts Cα1,Cα2,…,Cαk.Output:twG and achieving cuts.(1)
Step 1: use Algorithm 1 to find the union of minimal local cuts with nonempty intersection.(2)
Step 2: use Algorithm 2 to find the number of connected components.(3)
Step 3: for each cut X, compute wX/ωG−X.(4)
Step 4: compute minwX/ωG−X; output twG and achieving cuts.Figure 2
The weighted interval graphs (a)G1 and (b) G2.
(a)(b)Remark 2.
The weight ofG1 and G2 are randomly generated.


## 3. Conclusion Remarks

At last, we consider the complexity of Algorithm3. Let AG=aijn×n be the adjacency matrix of an interval graph G of order n. In Algorithm 3, computing wX and wX/ωG−X in Step 3 requires X−1 additions and 1 division. Since at most kk+1/2 cuts be considered, the total operations of Step 3 is at most kk+1/2X. Step 4 requires kk+1/2logkk+1/2 comparisons, where k≤n−2. Combining Theorem 4 and Theorem 5, the complexity of Algorithm 3 is On3. Therefore, it is a good algorithm.In this paper, we introduce a new parameter, weighted toughness, which generalizes the concept of toughness to weighted graphs. This parameter can be used to measure the invulnerability of weighted graphs. A polynomial algorithm for computing the weighted toughness of interval graphs is given.However, computing the weighted toughness for general graphs isNP-hard. Algorithms and complexity analysis of weighted toughness for graphs such as trees, chordal graphs, and permutation graphs may be interesting. We can also use other parameters to measure the invulnerability of weighted graphs.



---

*Source: 6657594-2021-01-29.xml*