# Weighted Maximum-Clique Transversal Sets of Graphs

Authors: Chuan-Min Lee
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

Amaximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-hereditary graphs, and graphs of bounded treewidth.


---

## Body

## 1. Introduction

All graphs considered in this paper are undirected,  finite,  and simple. LetG=(V,E) be a graph with vertex set V and edge set E. Unless stated otherwise,  it is understood that |V|=n and |E|=m. For a graph G,  we also use V(G) and E(G) to denote the vertex set and edge set of G,  respectively. A graph G′=(V′,E′) is a subgraph of G if V′⊆V and E′⊆E. We use G[W] to denote a subgraph of G  induced by a subset W of V,  that is,  G[W] is the subgraph with vertex set W in which two vertices are adjacent whenever they are adjacent in G. For any vertex v∈V,  the neighborhood of v in G is NG(v)={u∈V∣(u,v)∈E} and the closed neighborhood of v in G is NG[v]=NG(v)∪{v}. The degree of a vertex v in G,  denoted by degG(v),  is the number of edges incident with v. If degG(v)=0,  then v is an isolated vertex of G. A clique is a subset of pairwise adjacent vertices of V. A maximal clique is a clique that is not a proper subset of any other clique. We use C(G) to denote the collection of all maximal cliques of G. A clique is maximum if there is no clique of G of larger cardinality. The clique number of G,  denoted by ω(G),  is the cardinality of a maximum clique of G. We use Q(G) to denote the collection of all maximum cliques of G.Amaximum-clique transversal set of a graph G=(V,E) is a subset of V intersecting all maximum cliques of G. The maximum-clique transversal number of G,  denoted by τM(G),  is the minimum cardinality of a maximum-clique transversal set of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. A maximum-clique independent set of G is a collection of pairwise disjoint maximum cliques of G. The maximum-clique independence number,  denoted by αM(G),  is the maximum cardinality of a maximum-clique independent set of G. The maximum-clique independent set problem is to find a maximum-clique independent set of G of maximum cardinality.Maximum-clique transversal sets were introduced by Chang et al.  in 2001 [1]. One of the main objectives for their research on maximum-clique transversal sets is the placement of transmitter towers for cellular telephones. Chang et al.  stated a cellular telephone tower placement problem as the maximum-clique transversal set problem. They considered the problem and presented fixed parameter and approximation results for planar graphs. They also investigated the problem for some other graph classes such as k-trees,  strongly chordal graphs,  graphs with few P4s,  comparability graphs,  and distance-hereditary graphs. Recently,  Lee [2] introduced some variations of the maximum-clique transversal set problem and presented complexity results for them on some well-known classes of graphs.Maximum-clique transversal and maximum-clique independent sets are closely related toclique transversal and clique independent sets on graphs. A clique transversal set of a graph G=(V,E) is a subset of V intersecting all maximal cliques of G and a clique independent set of G is a collection of pairwise disjoint maximal cliques of G. The clique transversal number of G,  denoted by τC(G),  is the minimum cardinality of a clique transversal set of G. The clique independence number of G,  denoted by αC(G),  is the maximum cardinality of a clique independent set of G. The clique transversal (resp.,  independent) set problem is to find a clique transversal (resp.,  independent) set of G of minimum (resp.,  maximum) cardinality. The clique transversal and clique independent set problems have been widely studied in [1, 3–20].In this paper,  we study theweighted version of the maximum-clique transversal set problem. Let w:V→ℕ be a function assigning to each vertex v of G=(V,E) a weight w(v) such that all arithmetic operations on vertex weights can be performed in time O(1). We call w a vertex-weight function and call G=(V,E,w) a weighted graph. We let w(S)=∑u∈Sw(u) for any subset S of V and let w(S) be the weight of S. The weighted maximum-clique transversal set problem is to find a maximum-clique transversal set S of a weighted graph G=(V,E,w) such that w(S) is minimized.We present polynomial-time algorithms (most of them with linear running time) for the weighted maximum-clique transversal set problem on split graphs,  balanced graphs,  strongly chordal graphs,  Helly circular-arc graphs,  comparability graphs,  distance-hereditary graphs,  and graphs of bounded treewidth.


## 2. Split Graphs

In this section,  we consider the weighted maximum-clique transversal set problem on split graphs.Definition 2.1.
Asplit graph is a graph G=(I∪Q,E),  where the vertices of G can be partitioned into an independent set I and a clique Q.Throughout this section,  we useG=(V,E,w) to denote a split graph G with a vertex-weight function w. Without loss of generality,  we may assume that G has no isolated vertices and that the vertices of G have been partitioned into an independent set I and a maximum clique Q. We give Algorithm 1 to solve the weighted maximum-clique transversal set problem for a split graph G=(I∪Q,E,w).Algorithm 1:Finding a maximum-clique transversal set of a split graph of minimum weight.
Input: A split graph G=(I∪Q,E,w).Output: A maximum-clique transversal set D of G of minimum weight.(1)S=I;(2)for each vertex v∈Q  do(3)wN(v)=w(NG(v));(4)end  for(5)for each vertex s∈I  do(6)if  degG(s)<ω(G)-1  then(7)S←S∖{s};(8)for each v∈NG(s)  do(9)wN(v)=wN(v)-w(s);(10)end for(11)end if(12)end for(13) Find a vertexv1∈Q such that w(v1)=min{w(v)∣v∈Q};(14) Find a vertexv2∈Q∖{v1} such that w(v2)=min{w(v)∣v∈Q∖{v1}};(15) Find a vertexv3∈Q such that w(S∪Q)-wN(v3)=min{w(S∪Q)-wN(v)∣v∈Q};(16)ifmin{w(v1)+w(v2),w(S∪Q)-wN(v3)}=w(v1)+w(v2)  then(17)D={v1,v2};(18)else(19)D={v3}∪(S∖NG(v3));(20)end if(21) Output the setD;Theorem 2.2.
Algorithm1 finds a maximum-clique transversal set D of a split graph G=(I∪Q,E,w) of minimum weight in O(n+m) time.Proof.
The theorem holds trivially ifG has only one maximum clique. We may assume that G has more than one maximum clique. We show the correctness of Algorithm 1 as follows.
Initially,S=I and wN(v)=w(NG(v)) for each vertex v∈Q. At each iteration of Steps (5)–(12),  the algorithm removes from S an element s with degG(s)<ω(G)-1,  and wN(v) is decreased by the weight w(s) if v is adjacent to s. At the end of the last iteration of Steps (5)–(12),  the set S consists of all vertices s with degG(s)=ω(G)-1,  and wN(v)=w(NG(v)∩Q)+w(NG(v)∩S) for each vertex v∈Q.
For every maximum clique ofG other than Q,  it has exactly one vertex in I and ω(G)-1 vertices in Q. For a vertex x∈I with degG(x)<ω(G)-1,  NG[x] is not a maximum clique of G. Therefore,  Q(G)={Q}∪⋃s∈S{NG[s]}.
Assume thatD′ is a maximum-clique transversal set of G of minimum weight. Let x1 and x2 be two vertices in Q. For every maximum clique Q′ of G other than Q,  it has exactly one vertex in S and ω(G)-1 vertices in Q. It is clear that Q′ contains at least one vertex in {x1,x2} and thus D′ contains at most two vertices in Q.
Letv1 be a vertex in Q such that w(v1)=min{w(v)∣v∈Q}. Let v2 be a vertex in Q∖{v1} such that w(v2)=min{w(v)∣v∈Q∖{v1}} and let v3 be a vertex in Q such that w(S∪Q)-wN(v3)=min{w(S∪Q)-wN(v)∣v∈Q}. We consider the following two cases.Case 1 (|D′∩Q|=2).
It can be easily verified that the set{v1,v2} is a maximum-clique transversal set of G of minimum weight,  and thus w(D′)=w(v1)+w(v2).Case 2 (|D′∩Q|=1).
LetD′∩Q={v′} and let D*={v′}∪(S∖NG(v′)). If S∖NG(v′)=∅,  then v′ is adjacent to every vertex in S. We have w(D′)=w(D*)=w(v′). Suppose that S∖NG(v′)≠∅. For any vertex x∈S∖NG(v′),  the maximum clique NG[x] does not contain the vertex v′. Since D′ does not contain any vertex in Q∖{v′},  x must be included in D′. In other words,  the set S∖NG(v′) is a subset of D′. Then,  the set D*={v′}∪(S∖NG(v′)) is a maximum-clique transversal set of G and w(D′)=w(D*). Note that S∩Q=∅ and wN(v′)=w(NG(v′)∩Q)+w(NG(v′)∩S). We have
(2.1)w(S∪Q)-wN(v′)=w(S)+w(Q)-(w(NG(v′)∩Q)+w(NG(v′)∩S))=(w(S)-w(NG(v′)∩S))+(w(Q)-w(NG(v′)∩Q))=w(S∖NG(v′))+w(v′)=w(D*).
Since w(S∪Q)-wN(v3)=min{w(S∪Q)-wN(v)∣v∈Q},  the set D={v3}∪(S∖NG(v3)) is a maximum-clique transversal set of G of minimum weight. Following the discussion above,  the algorithm is correct.
Clearly,  Step (1) and Steps (13)–(21) of Algorithm1 can be done in O(n) time. Steps (2)–(4) and Steps (5)–(12) can be done in O(∑v∈V(G)(degG(v)+1))=O(n+m) time. Hence,  the running time of the algorithm is O(n+m) time.


## 3. Balanced Graphs

In this section,  we consider the weighted maximum-clique transversal set problem on balanced graphs.LetG be a graph. Suppose that V(G)={v1,v2,…,vn},  C(G)={C1,C2,…,Cp},  and Q(G)={Q1,Q2,…,Qℓ}. A clique matrix (resp.,  maximum-clique matrix) of G,  is the (0,1)-matrix whose entry (i,j) is 1 if vj∈Ci (resp.,  vj∈Qi),  and 0 otherwise. A (0,1)-matrix is balanced if it does not contain the vertex-edge incidence matrix of an odd cycle as a submatrix,  or equivalently,  if it does not contain a square submatrix of odd order with exactly two ones per row and column. A (0, 1)-matrix is totally balanced if it does not contain the vertex-edge incidence matrix of a cycle as a submatrix [21]. A graph G is balanced (resp.,  totally balanced) if a clique matrix of G is balanced (resp.,  totally balanced).Balanced graphs have been considered in [2, 8, 12, 15, 22]. It can be easily verified that if a clique matrix of a graph G is balanced (resp.,  totally balanced),  then all clique matrices of G are balanced (resp.,  totally balanced). Note that a maximum-clique matrix of a graph G is a submatrix of some clique matrix of G. By definition,  a submatrix of a balanced matrix is also balanced. We have the following lemma.Lemma 3.1.
If a graphG is balanced,  then any maximum-clique matrix of G is balanced.Let 1 (resp.,  0) be a vector withn 1’s (resp.,  0’s) and let x=(x1,x2,…,xn) be a column vector. Let G=(V,E,w) be a weighted graph with V={v1,v2,…,vn}. Suppose that M is a maximum-clique matrix of G. The weighted maximum-clique transversal set problem for G can be formulated as the following integer linear programming problem:(3.1)Minimize∑i=1nw(vi)⋅xisubjecttoMx≥1xi=1or0fori=1,2,…,n.Fulkerson et al. proved the following important property of balanced matrices.Theorem 3.2 (Fulkerson et al. [22]).
IfA is a balanced matrix,  then the polyhedra P1(A)={x∣Ax≥1,x≥0}  and P2(A)={x∣Ax≤1,x≥0}  have only integer extreme points.Theorem 3.3.
For any weighted balanced graphG,  the weighted maximum-clique transversal set problem can be solved in polynomial time.Proof.
Balanced graphs are a subclass ofhereditary clique-Helly graphs [8]. Prisner [23] showed that no connected hereditary clique-Helly graphs has more maximal cliques than edges. Then, a connected balanced graph has O(m) maximal cliques. Since all maximal cliques of a hereditary clique-Helly graph can be enumerated in polynomial time by the algorithms in [24],  all the maximum cliques can be extracted in polynomial time. Therefore,  a maximum-clique matrix M of G can be computed in polynomial time.
Note that if the extreme points of the polyhedra defined by the linear relaxation of an integer linear programming problem are integers,  then the optimal solution of the integer linear programming problem is equal to the optimal solution of its linear relaxation. It is wellknown that linear programming problems can be solved in polynomial time. Following Lemma3.1 and Theorem 3.2,  the weighted maximum-clique transversal set problem is polynomial-time solvable for balanced graphs.


## 4. Strongly Chordal Graphs

In this section,  we consider the weighted maximum-clique transversal set problem for strongly chordal graphs.LetG=(V,E) be a graph. A vertex v is simplicial if all vertices of NG[v] form a clique. The ordering (v1,v2,…,vn) of the vertices of V is a perfect elimination ordering of G if for all i∈{1,…,n},  vi is a simplicial vertex of the subgraph Gi of G induced by {vi,vi+1,…,vn}. Let Ni[v] denote the closed neighborhood of v in Gi. Rose [25] showed the characterization that a graph is chordal if and only if it has a perfect elimination ordering. A perfect elimination ordering is called a strong elimination ordering if the following condition is satisfied.Fori≤j≤k if vj and vk belong to Ni[vi] in Gi,  then Ni[vj]⊆Ni[vk].Farber [26] showed that a graph is strongly chordal if and only if it admits a strong elimination ordering. So far,  the fastest algorithm to recognize a strongly chordal graph and give a strong elimination ordering takes O(mlogn) [27] or O(n2) time [28].Definition 4.1.
LetG=(V,E) be a graph and Q(G)={Q1,Q2,…,Qℓ}. Let X(G)=⋃i=1ℓQi. The 𝒱𝒬-incidence graph of G,  denoted by ℋ′(G),  is defined as follows. The vertex set of ℋ′(G) is X(G)∪S′(G) where S′(G)={s1′,s2′,…,sℓ′}. In ℋ′(G),  (1) S′(G) is an independent set,  (2) two vertices of X(G) are adjacent if they are adjacent in G,  and (3) for 1≤i≤ℓ,  si′∈S′(G) is adjacent to vj∈X(G) if vj∈Qi in G.Definition 4.2.
Adominating setS of a graph G is a subset of V(G) such that |S∩NG[v]|≥1 for every vertex v∈V(G). The domination number of G,  denoted by γ(G),  is the minimum cardinality of a dominating set of G. The weighted dominating set problem is to find a dominating set S of a weighted graph G=(V,E,w) such that w(S) is minimized.Lemma 4.3.
LetG=(V,E,w) be a weighted graph. Let wℋ′ be a vertex-weight function of ℋ′(G) defined by wℋ′(v)=∞ if v∈S′(G) and wℋ′(v)=w(v) if v∈X(G). A maximum-clique transversal set of G of minimum weight is equivalent to a dominating set of ℋ′(G) of minimum weight.Proof.
Letτ̃M be the minimum weight of a maximum-clique transversal set of G and let γ̃ be the minimum weight of a dominating set of ℋ′(G).
Suppose thatD̂ is a maximum-clique transversal set of G of minimum weight. Then every maximum clique of G has at least one vertex in D̂. By the construction of ℋ′(G),  a vertex s′∈S′(G) is adjacent to the vertices of a maximum clique of G. Therefore,  D̂ is a dominating set of ℋ′(G). We have γ̃≤τ̃M.
Conversely,  we letD be a dominating set of ℋ′(G) of minimum weight. Clearly,  D does not contain any vertex in S′(G). For any vertex s∈S′(G),  the set D has a vertex in Nℋ′(G)(s). By the construction of ℋ′(G),  Nℋ′(G)(s) is a maximum clique of G. Therefore,  D is a maximum-clique transversal of G. We have τ̃M≤γ̃.
Following the discussion above,τ̃M=γ̃ and thus the lemma holds.Lemma 4.4.
LetG be a strongly chordal graph. Then ℋ′(G) is a strongly chordal graph,  and a strong elimination ordering of ℋ′(G) can be obtained from a strong elimination ordering of G in O(n+m) time.Proof.
A strongly chordal graph is chordal. It has at mostn maximal cliques,  and all of its maximal cliques can be enumerated in O(n+m) time [29]. Then,  all maximum cliques Q1,Q2,…,Qℓ of a strongly chordal graph can be enumerated in O(n+m) time.
LetC(G)={C1,C2,…,Cp} and S(G)={s1,s2,…,sp}. The vertex-clique incidence graph of G,  denoted by ℋ(G),  is defined as follows. The vertex set of ℋ(G) is V(G)∪S(G). In ℋ(G),  (1) S(G) is an independent set,  (2) two vertices of V are adjacent if they are adjacent in G,  and (3) for 1≤i≤p,  si∈S(G) is adjacent to vj∈V(G) if vj∈Ci in G. Let S′ be a maximum subset of S(G) such that Nℋ(G)(s′) is a maximum clique of G for each vertex s′∈S′. Note that Q(G)⊆C(G) and X(G)⊆V(G). Therefore,  ℋ′(G) is isomorphic to the subgraph of ℋ(G) induced by X(G)∪S′.
Guruswami and Rangan [17] showed that ℋ(G) is a strongly chordal graph with O(n+m) edges and O(n) vertices,  and that a strong elimination ordering of ℋ(G) can be obtained from a given one for G in O(n+m) time. Therefore,  ℋ′(G) is also a strongly chordal graph and can be constructed from ℋ(G) in O(n+m) time.
Suppose thatn1=|V(ℋ(G))| and n2=|V(ℋ′(G))|. Then,  n2≤n1. Let (w1,w2,…,wn1)  be a strong elimination ordering of ℋ(G). Let (wx1,wx2,…,wxn2) be the ordering of the vertices in ℋ′(G) obtained by removing all the vertices in V(ℋ(G))∖V(ℋ′(G)) from the ordering (w1,w2,…,wn1). It can be easily verified that the ordering (wx1,wx2,…,wxn2) is also a strong elimination ordering of ℋ′(G). Following the discussion above,  the lemma holds.Theorem 4.5.
The weighted maximum-clique transversal set problem can be solved inO(n+m) time for a strongly chordal graph G if a strong elimination ordering is given.Proof.
It follows from Lemmas4.3 and 4.4 and the result that the weighted dominating set problem can be solved in O(n+m) time for a strongly chordal graph if a strong elimination ordering is given [30].


## 5. Helly Circular-Arc Graphs

In the section,  we consider the weighted maximum-clique transversal set problem for Helly circular-arc graphs.Definition 5.1.
Let𝒮 be a set. Let 𝒫 be a set of some positive integers. A collection {Si}i∈𝒫 of subsets of 𝒮 is said to satisfy the Helly property if J⊆𝒫 and Si∩Sj≠∅ for all i,j∈J implies ⋂j∈JSj≠∅.Letℱ be a collection of nonempty sets. The intersection graphG of ℱ is obtained by representing each set in ℱ as a vertex and connecting two vertices with an edge if and only if their corresponding sets intersect. A circular-arc modelℳ is a pair (𝒞,𝒜),  where 𝒞 is a circle and 𝒜 is a collection of arcs of 𝒞. If a graph G is the intersection graph of 𝒜,  then G is a circular-arc graph. If 𝒜 satisfies the Helly property,  then G is a Helly circular-arc graph and ℳ is called a Helly circular-arc model of G. For an arc A∈𝒜,  let v(A) be the vertex of G corresponding to A. For 𝒜′⊆A,  let V(𝒜′)=⋃A∈𝒜′{v(A)}. Let p be a point of 𝒞 and let 𝒜(p) be the collection of arcs that contain p. If V(𝒜(p)) is a maximal clique of G,  then p is called a clique point. Suppose that p1 and p2 are distinct points of 𝒞. If 𝒜(p1)=𝒜(p2),  then p1 and p2 are equivalent. A clique point representation of ℳ is a maximum set of nonequivalent clique points of 𝒞.Letℳ=(𝒞,𝒜) be a circular-arc model of a Helly circular-arc graph G. Let X be a maximal clique of G and let 𝒲={c1,c2,…,cp} be a clique point representation of ℳ. Due to Helly property,  the arcs corresponding to vertices in X have a point on the circle 𝒞 in common. It is clear that a point b of 𝒞 is a clique point if and only if V(𝒜(b)) is a maximal clique of G. Then,  we have C(G)={V(𝒜(c1)),V(𝒜(c2)),…,V(𝒜(cp))}.Ifs and t are points of 𝒞,  we use (s,t) to denote an arc of 𝒜 starting at s and ending at t in clockwise direction. For each arc A=(s,t)∈𝒜,  the points s,t are called the extremes of A. We also use s(A) and t(A) to denote the starting point and ending point of the arc A,  respectively. Without loss of generality,  we assume that (1) all arcs of 𝒞 are open arcs,  (2) no single arc entirely covers 𝒞,  and (3) no two extremes of distinct arcs of 𝒜 coincide.Let𝒜={A1,A2,…,An} and Ai=(si,ti) for 1≤i≤n. An intersection segment(si,tj) is the contiguous part of 𝒞 formed by two consecutive extremes si and tj,  where si is the starting point of some arc Ai∈𝒜 and tj is the ending point of an arc Aj∈𝒜 in clockwise direction. A point inside an intersection segment is called an intersection point. There are at most n intersection segments and every clique point is an intersection point [13].LetH be a weighted Helly circular-arc graph with a Helly circular-arc model ℳ=(𝒞,𝒜). Lin et al. [31] proposed a linear-time algorithm that finds a clique point representation 𝒲 of ℳ. Based upon their algorithm,  we have the following theorem.Theorem 5.2.
Letℳ=(𝒞,𝒜) be a Helly circular-arc model of a Helly circular-arc graph G. Let 𝒲={c1,c2,…,cp} be a clique point representation of ℳ. Then,  the clique number ω(G) and 𝒜(c1),𝒜(c2),…,𝒜(cp) can be computed in linear time.Guruswami and Rangan [17] showed that a Helly circular-arc graph G has at most n maximal cliques. The following lemma can be easily verified according to the Helly property.Lemma 5.3.
Suppose thatG is a Helly circular-arc graph with a Helly circular-arc model ℳ=(𝒞,𝒜) and ω(G)>1. Let v be a vertex of G. Then,  there are at most degG(v) maximal cliques of G containing the vertex v.Lemma 5.4.
Suppose thatG=(V,E) is a Helly circular-arc graph with a Helly circular-arc model (𝒞,𝒜).(1)
The𝒱𝒬-incidence graph ℋ′(G) has O(n+m) edges and O(n) vertices.(2)
The𝒱𝒬-incidence graph ℋ′(G) is a Helly circular-arc graph and a Helly circular-arc model (𝒞,𝒜′) of ℋ′(G) can be obtained from (𝒞,𝒜) in O(n+m) time.Proof.
(1) By Definition4.1,  V(ℋ′(G))=X(G)∪S′(G). Since G is a Helly circular-arc graph,  it has at most n maximal cliques [17]. Then ℋ′(G) has O(n) vertices. Without loss of generality,  we assume that the clique number ω(G)>1. By Lemma 5.3 and the construction of ℋ′(G),  every vertex v∈X(G) is adjacent to at most degG(v) vertices in S′(G). Hence,  the number of E(ℋ′(G)) is O(m+∑v∈X(G)(degG(v)+1))=O(n+m).
(2) Let𝒲={c1,c2,…,cp} be a clique point representation of ℳ. The clique point representation 𝒬 can be constructed in linear time [31]. Following Theorem 5.2,  the clique number ω(G) and the arc sets 𝒜(c1),𝒜(c2),…,𝒜(cp) can be computed in linear time. Then C(G)={V(𝒜(c1)),V(𝒜(c2)),…,V(𝒜(cp))}.
LetP={p1,p2,…,pℓ} be a maximum subset of 𝒬 such that V(𝒜(pi)) is a maximum clique of G for 1≤i≤ℓ. The set P and the arc sets 𝒜(p1),𝒜(p2),…,𝒜(pℓ) can be computed in linear time. Then Q(G)={V(𝒜(p1)),V(𝒜(p2)),…,V(𝒜(pℓ))}.
Let𝒜P=⋃i=1ℓ𝒜(pi) and let AW be a set of ℓ arcs of 𝒞 such that each arc of 𝒜W contains exactly one clique point of P and contains no extremes of arcs of 𝒜P. It follows that ℋ′(G) is a Helly circular-arc graph and (𝒞,𝒜P∪𝒜W) is a Helly circular-arc graph model for ℋ′(G). Hence,  ℋ′(G) is a Helly circular-arc graph,  and a Helly circular-arc model (𝒞,𝒜′) of ℋ′(G) can be obtained from (𝒞,𝒜) in O(n+m) time.Theorem 5.5.
The weighted maximum-clique transversal set problem can be solved inO(n+m) time for a Helly circular-arc graph G=(V,E,w) if a Helly circular-arc model ℳ=(𝒞,𝒜) is given.Proof.
It follows from Lemmas4.3 and 5.4,  and the result that the weighted dominating set problem can be solved in O(n+m) time for a circular-arc graph if a circular-arc model is given [32].


## 6. Comparability Graphs

Adirected graph (or just digraph) D=(V,A) consists of a nonempty finite set V of vertices and a finite set A of ordered pairs of distinct vertices called arrows. We call V the vertex set and A the arrow set of D. We also use V(D) and A(D) to denote the vertex set and arrow set of D,  respectively. For an arrow 〈u,v〉,  the first vertex u is its tail and the second vertex v is its head. We also say that the arrow 〈u,v〉leavesu and entersv. For a vertex v of D,  we use the following notations:(6.1)ND+(v)={w∈V∖{v}∣〈v,w〉∈A},ND-(v)={u∈V∖{v}∣〈u,v〉∈A}.
The sets ND+(v),ND-(v),  and ND(v)=ND+(v)∪ND-(v) are called the outneighborhood,  inneighborhood,  and neighborhood of v,  respectively. We call the vertices in ND+(v),ND-(v), and ND(v) the outneighbors,  inneighbors,  and neighbors of v,  respectively.Adirected walk in a digraph D=(V,A) from vertex u to vertex v,  or simply a directed(u,v)-walk is a sequence of vertices (v0,v1,…,vn) such that u=v0,v=vn, and 〈vi-1,vi〉 is an arrow in D for 1≤i≤n,  where n is called the length of this walk. A directed path is a directed walk in which no vertex is repeated. A directed (s,t)-path is directed path starting at s and ending at t. A directed Hamiltonian path is a directed path that visits each vertex of D exactly once. A directed cycle is a directed (v,v)-walk in which no vertex is repeated except v. Arrow set A is a transitive relation on V if for all u,v,w∈V,  the following holds:(6.2)If〈u,v〉∈Aand〈v,w〉∈A,then〈u,w〉∈A.LetG=(V,E) be an undirected graph. Then the directed graph D=(V,A) is an orientation of G if for all (x,y)∈E, either 〈x,y〉∈A or 〈y,x〉∈A and for all 〈x,y〉∈A, (x,y)∈E holds. If A is a transitive relation on V,  then D is a transitive orientation of G. If there are no directed cycles in D, then D is an acyclic orientationof G. Assume that D′=(V′,A′) is a directed graph. An undirected graph G=(V′,E) is the underlying graph of D′ if for all 〈x,y〉∈A′, (x,y)∈E and for all (x,y)∈E, either 〈x,y〉∈A′ or 〈y,x〉∈A′.An undirected graphG is a comparability graph if and only if it has a transitive orientation. Figure 1 shows a comparability graph  G and its transitive orientation.(a) A comparability graphG. (b) A transitive orientation of G.
(a)(b)Given a comparability graphG=(V,E), a transitive orientation of G can be found in linear time [33]. Chang et al. [1] solved the maximum-clique transversal set problem in O(mn) time for comparability graphs. In this section, we show how to use a transitive orientation of a comparability graph G=(V,E) to solve the weighted maximum-clique transversal set problem on G in O(nmlog(n2/m)) time.Definition 6.1.
Atournament is an orientation of a complete graph.Theorem 6.2 (Rédei [34]).
Every tournament contains a directed Hamiltonian path.Lemma 6.3.
There exists a one-to-one correspondence between the set of maximum cliques of a comparability graphG and the set of longest directed paths of a transitive orientation D of G.Proof.
LetG=(V,E) be a comparability graph and let D=(V,A) be a transitive orientation of G. By the transitive relation on V,  each directed path in D corresponds to a clique of G. Let (v1,v2,…,vk) be a longest directed path of D. If S={v1,v2,…,vk} is not a maximum clique of G,  then there exists a vertex v∈V∖S such that S∪{v} is a clique of G. With the help of Theorem 6.2,  we know that there is a directed path of length k+1. However,  it contradicts that the length of a longest directed path is k. Hence,  each longest directed path of D corresponds to a maximum clique of G.
Conversely,  letS={v1,v2,…,vk} be a maximum clique of G. With the help of Theorem 6.2,  we know that there exists a directed path P of length k. Assume that P is not a longest directed path in D. Then there exists a path of length greater than k. By the transitive relation on V,  there is a clique whose number of vertices is larger than k. However,  it contradicts that S is a maximum clique of G. Hence,  each maximum clique of G corresponds to a longest directed path in D. Following the discussion above,  the lemma holds.Suppose thatG=(V,E) is a comparability graph and D=(V,A) is a transitive orientation of G. By the transitive relation on V,  D has no directed cycle. It is known that an acyclic digraph H has a topological sort of V(H),  that is,  a linear ordering of all vertices in V(H) such that if H contains an arrow 〈u,v〉∈A,  then u precedes v in the ordering [35]. Clearly,  there exists at least one vertex u such that no vertex enters it. We call such vertices the source vertices. Similarly,  there exists at least one vertex v such that no vertex leaves it. Such vertices are called the sink vertices. We add a new vertex s to D and add arrows from s to every source vertex in D. Correspondingly we add another new vertex t and arrows from every sink vertex in D to t. Let D′=(V′,A′) be the resulting digraph. The digraph D′ is called an (s,t)-transitive orientation of G.Lemma 6.4.
Every longest directed path in a transitive orientationD of a comparability graph G=(V,E) starts at a source vertex and ends at a sink vertex.Proof.
It can be easily verified according to the transitive relation onV and the definition of a longest directed path.Lemma 6.5.
LetG=(V,E) be a comparability graph and let D be a transitive orientation of G. Suppose that D′ is the (s,t)-transitive orientation of G. Let P=(s=v0,v1,v2,…,vi-1,vi=t) be an arbitrary directed (s,t)-path in D′. Directed path P has the longest length if and only if the path (v1,v2,…,vi-1) is a longest directed path in D.Proof.
It can be easily verified by Lemma6.4.Definition 6.6.
LetG=(V,E) be an undirected graph. A vertex set S⊂V is a vertex separator of G if G[V∖S] is disconnected. A set S⊂V is an (a,b)-vertex separator of G if a and b are in distinct connected components of G[V∖S].In [1],  Chang et al. remove some vertices (except for s and t) and arrows from an (s,t)-transitive orientation D′ of a comparability graph G to obtain a new digraph D* such that (1) every directed (s,t)-path in D* is a longest directed path in D′ and (2) every longest directed path in D′ is a directed (s,t)-path in D*. The construction of D* can be done in linear time. We call D* the (s,t)-longest-path digraph of G. By Lemmas 6.3 and 6.5,  a subset S of V(G) is a maximum clique if and only if s,  t,  and all vertices in S can form a directed (s,t)-path in D*. Therefore,  we have the following theorem.Theorem 6.7.
LetG be a comparability graph with a vertex-weight function w and let D* be an (s,t)-longest-path digraph of G. Suppose that G* is the underlying graph of D*. An (s,t)-vertex separator S of G* of minimum weight w(S) is equivalent to a maximum-clique transversal set of G of minimum weight.Definition 6.8.
LetD=(V,A) be a flow network with a capacity function c. Let s be the source vertex of the network,  and let t be the sink vertex. Let S be a subset of vertices such that s∈S and t∈V∖S. Let S¯=V∖S. We use (S;S¯) to denote the set of arrows which leave from a vertex of S and enter a vertex of S¯. The (S;S¯) is called a cut of D. Let c(S)=∑e∈(S;S¯)c(e) be the capacity of the cut determined by S. A minimum cut S is a cut of D such that c(S) is minimized.Theorem 6.9 (Max-flow min-cut theorem [36, 37]).
In every network,  the maximum total value of a flow equals the minimum capacity of a cut.Suppose thatG is a comparability graph with a vertex-weight function w and D* is an (s,t)-longest-path digraph of G. We construct a flow networkD̂=(V̂,Â) from D* as follows:(1)
V̂={s,t}∪{v1,v2∣v∈V(D*)∖{s,t}};(2)
Â=A1∪A2∪A3∪A4,  where A1={〈s,v1〉∣〈s,v〉∈A(D*)},  A2={〈v1,v2〉∣v∈V(D*)∖{s,t}},  A3={〈u2,v1〉∣〈u,v〉∈A(D*) and u,v∈V(D*)∖{s,t}},  and A4={〈v2,t〉∣〈v,t〉∈A(D*)};(3)
For each arrow〈v1,v2〉∈A2,  let the weight w(v) be its capacity. For each edge in A1∪A3∪A4,  we assign the capacity ∞ to it.Let(S;S¯) be a minimum cut of D̂. By the max-flow min-cut theorem,  (S;S¯) does not contain any arrow in A1∪A3∪A4. The set (S;S¯) is a subset of A2. Suppose that (S;S¯)={〈xℓ11,xℓ12〉,〈xℓ21,xℓ22〉,…,〈xℓi1,xℓi2〉}. Let S′={xℓ1,xℓ2,…,xℓi}. It can be easily verified that S′ is an (s,t)-vertex separator of G* of minimum weight. Following Theorem 6.7,  we know that the set S′ is a maximal-clique transversal set of G of minimum weight. Note that a minimum cut of a flow network can be computed in O(nmlog(n2/m)) time [38]. Therefore,  we have the following result.Theorem 6.10.
Given a comparability graphG with a vertex-weight function w,  the weighted maximum-clique transversal set problem can be solved in O(nmlog(n2/m)) time.


## 7. Graphs of Bounded Treewidthk

In this section we show that the weighted maximum-clique transversal set problem can be solved in linear time for graphs of bounded treewidth.A clique withk vertices is called a k-clique. A (k+1)-clique is a k-tree. A k-tree with n+1 vertices can be obtained from a k-tree with n vertices by making a new vertex adjacent to exactly all vertices of a k-clique. For a k-tree G,  ω(G)=k if G is a k-clique and ω(G)=k+1 otherwise. For convenience,  we define k-trees as having at least k+1 vertices. With this definition,  the treewidth of a k-tree is k and the clique number of a k-tree is k+1. Then,  a k-clique is a (k-1)-tree and the treewidth of a k-clique is k-1.Subgraphs ofk-trees are called partialk-trees. If a partial k-tree G is a subgraph of a k-tree H,  then we call H a k-tree embedding for G. The smallest k such that a graph G is a partial k-tree is called the treewidth of G. It is clear that a graph of treewidth k is also a partial ℓ-tree for every ℓ≥k. The class of partial k-trees is exactly the class of graphs of treewidth at most k.The treewidth of a graph can be defined by the concept oftree decompositions of a graph (see, e.g.,  [39]).Definition 7.1.
Atree decomposition of a graph G=(V,E) is a pair (T,𝒮),  where T is a tree with ℓ nodes and 𝒮 is a collection of subsets S1,S2,…,Sℓ of V such that a node i in T corresponds to the subset Si∈𝒮 for 1≤i≤ℓ and the following three conditions are satisfied.(1)
Every vertexx∈V appears in at least one subset Si∈𝒮.(2)
For every edgee∈E,  there is at least one subset Si∈𝒮 containing both endpoints of e.(3)
If a vertexx appears in two subsets Si,Sj∈𝒮,  then it appears in every subset Sk for k on the (unique) path from node i to node j in T.Definition 7.2.
Thewidth of a tree decomposition (T,𝒮) of a graph G is the maximum cardinality minus one over all subsets of 𝒮. The treewidth of a graph G is the minimum width over all tree decompositions of G.Lemma 7.3 (Bodlaender [40]).
If the treewidth of a graphG=(V,E) is at most k,  then |E|≤k|V|-(1/2)k(k+1).By Lemma7.3,  O(|V|+|E|)=O(kn) for a partial k-tree G=(V,E) with bounded k. It was shown in [40] that for each constant k it can be determined in linear time whether a graph G has treewidth at most k.A tree decomposition(T,𝒮) is rooted if the tree T is equipped with some root node. A rooted tree decomposition is called nice if the following conditions are satisfied.(1)
Every node ofT has at most two children.(2)
If a nodei has two children j and k then Si=Sj=Sk.(3)
If a nodei has only one child j then either |Si|=|Sj|+1 and Sj⊂Si or |Si|=|Sj|-1 and Si⊂Sj.By [39],  it is fairly easy to see that every graph with treewidth k has a nice tree decomposition of width k and that it can be obtained in linear time from an ordinary tree decomposition with the same width. Furthermore any graph on n vertices has a nice tree decomposition with at most 4n nodes. In the following,  we assume that a nice tree decomposition (T,𝒮) of G of width k is part of the input.Lemma 7.4 (Bodlaender and Möhring [41]).
Let(T,𝒮) be a tree decomposition for a graph G. For every clique C of G,  there exists a subset X∈𝒮 such that C is a subset of X.Lemma 7.5.
Given a nice tree decomposition(T,𝒮) of a graph G of bounded treewidth k,  the maximum cliques of G=(V,E) can be enumerated in O(3k/3n) time.Proof.
Note that a nice tree decomposition of a graph of bounded treewidthk has at most 4n nodes. In other words,  𝒮 contains at most 4n subsets of V. Let 𝒮={S1,S2,…,Sℓ}. For 1≤i≤ℓ,  |Si|≤k+1. By Lemma 7.4,  a maximum clique is contained in a subset Si∈𝒮. For each Si∈𝒮,  all maximal cliques of G[Si] can be enumerated in O(3k/3) time by the algorithm in [42]. Therefore,  all maximum cliques of G can be extracted in O(3k/3n) time.Lemma 7.6.
Suppose thatG is a graph of bounded treewidth k with a nice tree decomposition (T,𝒮).(1)
The𝒱𝒬-incidence graph ℋ′(G) is a partial (k+1)-tree.(2)
A tree decomposition of the𝒱𝒬-incidence graph ℋ′(G) can be constructed in linear time.Proof.
Clearly,ω(G)≤k+1 and G is also a partial (k+1)-tree. By Definition 4.1,  V(ℋ′(G))=X(G)∪S′(G),  and each vertex in S′(G) is adjacent to all vertices of exactly one maximum clique of G. It can be easily verified that there exists a (k+1)-tree H′ such that V(H′)=V(G)∪S′(G) and ℋ′(G) is a subgraph of H′. Therefore,  ℋ′(G) is a partial (k+1)-tree. It was shown in [40] that for each constant k there is a linear-time algorithm for finding a treewidth decomposition for a graph of bounded treewidth k. Hence,  a tree decomposition of ℋ′(G) can be constructed in linear time. Following the discussion above,  the lemma holds.Theorem 7.7.
The weighted maximum-clique transversal set problem can be solved inO(4kn) time for a graph G of bounded treewidth k with a tree decomposition (T,𝒮).Proof.
Note that the weighted dominating set problem can be solved inO(4kn) time for a weighted graph G=(V,E,w) of bounded treewidth k if a tree decomposition of G is given [43]. By Lemmas 4.3,  7.5,  and 7.6,  the theorem holds.


## 8. Distance-Hereditary Graphs

This section deals with the weighted maximum-clique transversal set problem on distance-hereditary graphs. We show that the problem is linear-time solvable for distance-hereditary graphs.A graph isdistance-hereditary if any two distinct vertices have the same distance in every connected induced subgraph containing them. Chang et al. [44] showed that distance-hereditary graphs can be defined, recursively.Theorem 8.1 (Chang et al. [44]).
Distance-hereditary graphs can be defined recursively as follows.(1)
A graph consisting of only one vertex is distance-hereditary,  and the twin set is the vertex itself.(2)
IfG1 and G2 are disjoint distance-hereditary graphs with the twin sets TS(G1) and TS(G2),  respectively,  then the graph G=G1∪G2 is a distance-hereditary graph and the twin set of G is TS(G1)∪TS(G2). G is said to be obtained from G1 and G2 by a false twin operation.(3)
IfG1 and G2 are disjoint distance-hereditary graphs with the twin sets TS(G1) and TS(G2),  respectively,  then the graph G obtained by connecting every vertex of TS(G1) to all vertices of TS(G2) is a distance-hereditary graph,  and the twin set of G is TS(G1)∪TS(G2). G is said to be obtained from G1 and G2 by a true twin operation.(4)
IfG1 and G2 are disjoint distance-hereditary graphs with the twin sets TS(G1) and TS(G2),  respectively,  then the graph G obtained by connecting every vertex of TS(G1) to all vertices of TS(G2) is a distance-hereditary graph,  and the twin set of G is TS(G1). G is said to be obtained from G1 and G2 by a pendant vertex operation.By Theorem8.1,  a distance-hereditary graph G has its own twin set TS(G),  the twin set TS(G) is a subset of vertices of G,  and it is defined recursively. The construction of G from disjoint distance-hereditary graphs G1 and G2 as described in Theorem 8.1 involves only the twin sets of G1 and G2.Following Theorem8.1,  we can construct a binary ordered decomposition tree. In this decomposition tree,  each leaf is a single vertex graph,  and each internal node represents one of the three operations: pendant vertex operation (labeled by P),  true twin operation (labeled by T),  and false twin operation (labeled by F). This binary ordered decomposition tree is called a PTF-tree. It has 2n-1 tree nodes and can be obtained in linear time [44].Definition 8.2.
LetG=(V,E) be a distance-hereditary graph and let TS(G) be the twin set of G. We use Q(G) to denote the collection of maximum cliques of G. Therefore Q(G[TS(G)]) is the collection of all maximum cliques of G[TS(G)]. Let QE(G)=Q(G)∪Q(G[TS(G)]). The set QE(G) denotes the collection of all maximum cliques of G and all maximum cliques of G[TS(G)].Definition 8.3.
Suppose thatG is a distance-hereditary graph obtained from two disjoint distance-hereditary graphs G1 and G2 by a true twin operation or a pendant vertex operation. We use QX12(G) to denote the set {Q1∪Q2∣Q1∈Q(G1[TS(G1)]) and Q2∈Q(G2[TS(G2)])}.Lemma 8.4.
LetG be a distance-hereditary graph obtained from two disjoint distance-hereditary graphs G1 and G2 by a true twin operation or a pendant vertex operation. Then QX12(G)=Q(G[TS(G1)∪TS(G2)]).Proof.
This lemma can be easily proved by contradiction.Lemma 8.5.
SupposeG is a graph obtained from two disjoint distance-hereditary graphs G1 and G2 by a true twin operation or a pendant vertex operation. Let 𝒮 be a subset of V(G) such that 𝒮 intersects with all maximum cliques of G[TS(G1)∪TS(G2)]. Then either 𝒮∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] or 𝒮∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)].Proof.
Assume for contrary that neither𝒮∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] nor 𝒮∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)]. There exist maximum cliques Q1 and Q2 of G1[TS(G1)] and G2[TS(G2)],  respectively,  such that 𝒮 does not contain any vertex in them. By Lemma 8.4,  Q1∪Q2 is a maximum clique of G[TS(G1)∪TS(G2)]. Then,  𝒮 does not contain any vertex in Q1∪Q2,  which contradicts the assumption that 𝒮 intersects all maximum cliques of G[TS(G1)∪TS(G2)]. Following the discussion above,  the lemma holds.Definition 8.6.
LetG=(V,E,w) be a weighted graph. Suppose that W={V1,V2,…,Vℓ},  where Vi is a subset of V for 1≤i≤ℓ. Let minW be an element in W such that the weight of the element is minimum.In the paper [1],  Chang et al.  presented a linear-time algorithm for the maximum-clique transversal set problem. Based upon their algorithm,  we develop a linear-time algorithm to solve the weighted maximum-clique transversal set problem by the dynamic programming technique.For a distance-hereditary graphG=(V,E),  we use ω(G) (resp.,  ωt(G)) to denote the clique number of G (resp.,  G[TS(G)]) and use 𝒞𝒯(G) (resp.,  𝒞𝒯t(G)) to denote a maximum-clique transversal set of G (resp.,  G[TS(G)]) of minimum weight. A strong maximum-clique transversal setS of a distance-hereditary graph G is a subset of V(G) such that S intersects all cliques in QE(G). We use 𝒮𝒞𝒯(G) to denote a strong maximum-clique transversal set of G of minimum weight.Lemma 8.7.
Suppose thatG is a distance-hereditary graph of only one vertex v. Then,  ω(G)=ωt(G)=1,  and 𝒞𝒯(G)=𝒞𝒯t(G)=𝒮𝒞𝒯(G)={v}.Proof.
It follows from the definitions.Lemma 8.8.
Suppose thatG is formed from two disjoint distance-hereditary graphs G1 and G2 by a “false twin” operation.(1)
Ifωt(G1)=ωt(G2) and ω(G1)=ω(G2),  then ω(G)=ω(G1)=ω(G2),  ωt(G)=ωt(G1)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G1)∪𝒞𝒯t(G2),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1)∪𝒮𝒞𝒯(G2).(2)
Ifωt(G1)=ωt(G2) and ω(G1)>ω(G2),  then ω(G)=ω(G1),  ωt(G)=ωt(G1)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1),  𝒞𝒯t(G)=𝒞𝒯t(G1)∪𝒞𝒯t(G2),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1)∪𝒞𝒯t(G2).(3)
Ifωt(G1)=ωt(G2) and ω(G2)>ω(G1),  then ω(G)=ω(G2),  ωt(G)=ωt(G1)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G2)∪𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G2)∪𝒞𝒯t(G1).(4)
Ifωt(G1)>ωt(G2) and ω(G1)=ω(G2),  then ω(G)=ω(G1)=ω(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯v(G1)∪𝒞𝒯(G2).(5)
Ifωt(G2)>ωt(G1) and ω(G1)=ω(G2),  then ω(G)=ω(G1)=ω(G2),  ωt(G)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G2),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G2)∪𝒞𝒯(G1).(6)
Ifωt(G1)>ωt(G2) and ω(G1)>ω(G2),  then ω(G)=ω(G1),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G1),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1).(7)
Ifωt(G2)>ωt(G1) and ω(G2)>ω(G1),  then ω(G)=ω(G2),  ωt(G)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G2),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G2).(8)
Ifωt(G1)>ωt(G2) and ω(G1)<ω(G2),  then ω(G)=ω(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒞𝒯t(G1)∪𝒞𝒯(G2).(9)
Ifωt(G2)>ωt(G1) and ω(G2)<ω(G1),  then ω(G)=ω(G1),  ωt(G)=ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1),  𝒞𝒯t(G)=𝒞𝒯t(G2),  and 𝒮𝒞𝒯(G)=𝒞𝒯t(G2)∪𝒞𝒯(G1).Proof.
In the following,  we just show the correctness for Statement (4) since other statements can be verified in similar ways. Note thatG=G1∪G2 and TS(G)=TS(G1)∪TS(G2). Since ωt(G1)>ωt(G2) and ω(G1)=ω(G2),  ω(G)=ω(G1)=ω(G2),  and ωt(G)=ωt(G1). Therefore,  Q(G)=Q(G1)∪Q(G2) and Q(G[TS(G)])=Q(G1[TS(G1)]). We have 𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2) and 𝒞𝒯t(G)=𝒞𝒯t(G1).
By definition,QE(G)=Q(G)∪Q(G[TS(G)]) and thus QE(G)=Q(G1)∪Q(G2)∪Q(G1[TS(G1)]). Then QE(G)=QE(G1)∪Q(G2). Hence,  𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1)∪𝒞𝒯(G2). Following the discussion above,  the statement is true.Lemma 8.9.
Suppose thatG is formed from two disjoint distance-hereditary graphs G1 and G2 by a “pendant vertex” operation.(1)
Ifωt(G1)+ωt(G2)>max{ω(G1),ω(G2)},  then ω(G)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒞𝒯t(G1).(2)
Ifωt(G1)+ωt(G2)=ω(G1)>ω(G2),  then ω(G)=ω(G1)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G1),𝒞𝒯t(G2)∪𝒞𝒯(G1)},  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1).(3)
Ifωt(G1)+ωt(G2)=ω(G2)>ω(G1),  then ω(G)=ω(G2)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G2),𝒞𝒯t(G1)∪𝒞𝒯(G2)},  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒞𝒯t(G1)∪𝒞𝒯(G2).(4)
Ifωt(G1)+ωt(G2)=ω(G1)=ω(G2),  then ω(G)=ω(G1)=ω(G2)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)∪𝒞𝒯(G1)},  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1)∪𝒞𝒯(G2).(5)
Ifωt(G1)+ωt(G2)<ω(G1) and ω(G1)>ω(G2),  then ω(G)=ω(G1),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G1),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1).(6)
Ifωt(G1)+ωt(G2)<ω(G2) and ω(G2)>ω(G1),  then ω(G)=ω(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒞𝒯t(G1)∪𝒞𝒯(G2).(7)
Ifωt(G1)+ωt(G2)<ω(G2) and ω(G2)=ω(G1),  then ω(G)=ω(G1)=ω(G2),  ωt(G)=ωt(G1),  𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2),  𝒞𝒯t(G)=𝒞𝒯t(G1),  and 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G1)∪𝒞𝒯(G2).Proof.
In the following,  we just show the correctness for Statement (3) since other statements can be verified in similar ways.
By Theorem8.1,  TS(G)=TS(G1) and G is obtained from G1 and G2 by connecting every vertex of TS(G1) to all vertices of TS(G2). Therefore,  ωt(G)=ωt(G1) and 𝒞𝒯t(G)=𝒞𝒯t(G1).
We now considerω(G) and 𝒞𝒯(G). In this case,  ωt(G1)+ωt(G2)=ω(G2)>ω(G1). Then,  ω(G)=ω(G2)=ωt(G1)+ωt(G2) and thus Q(G)=Q(G2)∪QX12(G). Clearly,  𝒞𝒯(G) is a subset of TS(G1)∪V(G2) and 𝒞𝒯(G)∩V(G2) is a maximum-clique transversal set of G2. By Lemma 8.4,  we know that QX12(G)=G[TS(G1)∪TS(G2)]. Therefore,  𝒞𝒯(G) intersects all maximum cliques of G[TS(G1)∪TS(G2)]. By Lemma 8.5,  either 𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] or 𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)]. If 𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)],  then we have 𝒞𝒯(G)=𝒞𝒯(G2)∪𝒞𝒯t(G1). If 𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)],  then 𝒞T(G)∩V(G2) is not only a maximum-clique transversal set of G but also a strong maximum-clique transversal set of G2. We have 𝒞𝒯(G)=𝒮𝒞𝒯(G2). Hence,  𝒞𝒯(G)=min{𝒞𝒯t(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)}.
We now consider𝒮𝒞𝒯(G). By definition,  𝒮𝒞𝒯(G) intersects all maximum cliques in Q(G[TS(G)]) and Q(G),  respectively. Recall that TS(G)=TS(G1) and Q(G)=Q(G2)∪QX12(G). Therefore,  𝒮𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G[TS(G1)] and it also intersects all maximum cliques in QX12(G). Besides,  𝒮𝒞𝒯(G)∩V(G2) is a maximum-clique transversal set of G2. Hence,  𝒮𝒞𝒯(G)=𝒞𝒯t(G1)∪𝒞𝒯(G2).
Following the discussion above,  the statement is true.Lemma 8.10.
Suppose that a distance-hereditary graphG is formed from two disjoint distance-hereditary graphs G1 and G2 by a “true twin” operation. Let i∈{1,2}.(1)
Ifωt(G1)+ωt(G2)>max{ω(G1),ω(G2)},  then ω(G)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)}.(2)
Ifωt(G1)+ωt(G2)=ω(G1)>ω(G2),  then ω(G)=ω(G1)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G1),𝒞𝒯t(G2)∪𝒞𝒯(G1)},  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G1),𝒞𝒯t(G2)∪𝒞𝒯(G1)}.(3)
Ifωt(G1)+ωt(G2)=ω(G2)>ω(G1),  then ω(G)=ω(G2)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G2),𝒞𝒯t(G1)∪𝒞𝒯(G2)},  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G2),𝒞𝒯t(G1)∪𝒞𝒯(G2)}.(4)
Ifωt(G1)+ωt(G2)=ω(G1)=ω(G2),  then ω(G)=ω(G1)=ω(G2)=ωt(G1)+ωt(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=min{𝒮𝒞𝒯(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)∪𝒞𝒯(G1)},  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)∪𝒞𝒯(G1)}.(5)
Ifωt(G1)+ωt(G2)<ω(G1) and ω(G1)>ω(G2),  then ω(G)=ω(G1),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1),  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G1),𝒞𝒯(G1)∪𝒞𝒯t(G2)}.(6)
Ifωt(G1)+ωt(G2)<ω(G2) and ω(G2)>ω(G1),  then ω(G)=ω(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G2),  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G2),𝒞𝒯(G2)∪𝒞𝒯t(G1)}.(7)
Ifωt(G1)+ωt(G2)<ω(G2) and ω(G2)=ω(G1),  then ω(G)=ω(G1)=ω(G2),  ωt(G)=ωt(G1)+ωt(G2),  𝒞𝒯(G)=𝒞𝒯(G1)∪𝒞𝒯(G2),  𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)},  and 𝒮𝒞𝒯(G)=min{𝒮𝒞𝒯(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)∪𝒞𝒯(G1)}.Proof.
In the following,  we just show that the correctness for Statement (3) since other statements can be verified in similar ways.
By Theorem8.1,  TS(G)=TS(G1)∪TS(G2),  and G is obtained from G1 and G2 by connecting every vertex in TS(G1) to all vertices in TS(G2). By Lemma 8.4,  we have Q(G[TS(G)])=QX12(G). By Lemma 8.5,  either 𝒞𝒯t(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] or 𝒞𝒯t(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)]. Hence,  we have ωt(G)=ωt(G1)+ωt(G2) and 𝒞𝒯t(G)=min{𝒞𝒯t(G1),𝒞𝒯t(G2)}.
We now considerω(G) and 𝒞𝒯(G). In this case,  ωt(G1)+ωt(G2)=ω(G2)>ω(G1). Then,  ω(G)=ω(G2)=ωt(G1)+ωt(G2) and thus Q(G)=Q(G2)∪QX12(G). Clearly,  𝒞𝒯(G) is a subset of TS(G1)∪V(G2) and 𝒞𝒯(G)∩V(G2) is a maximum-clique transversal set of G2. Note that QX12(G)=G[TS(G1)∪TS(G2)]=G[TS(G)]. By Lemma 8.5,  either 𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] or 𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)]. If 𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)],  then we have 𝒞𝒯(G)=𝒞𝒯(G2)∪𝒞𝒯t(G1). If 𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)],  then 𝒞𝒯(G)∩V(G2) is not only a maximum-clique transversal set of G but also a strong maximum-clique transversal set of G2. We have 𝒞𝒯(G)=𝒮𝒞𝒯(G2). Hence,  𝒞𝒯(G)=min{𝒞𝒯t(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)}.
We now consider𝒮𝒞𝒯(G). By definition,  𝒮𝒞𝒯(G) intersects all maximum cliques in Q(G[TS(G)]) and Q(G),  respectively. Recall that QX12(G)=G[TS(G1)∪TS(G2)]=G[TS(G)] and Q(G)=Q(G2)∪QX12(G). Clearly 𝒮𝒞𝒯(G)∩V(G2) is a maximum-clique transversal set of G2.  By Lemma 8.5,  either 𝒮𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)] or 𝒮𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)]. If 𝒮𝒞𝒯(G)∩TS(G1) is a maximum-clique transversal set of G1[TS(G1)],  then we have 𝒮𝒞𝒯(G)=𝒞𝒯(G2)∪𝒞𝒯t(G1). If 𝒮𝒞𝒯(G)∩TS(G2) is a maximum-clique transversal set of G2[TS(G2)],  then 𝒮𝒞𝒯(G)∩V(G2) is not only a strong maximum-clique transversal set of G but also a strong maximum-clique transversal set of G2. We have 𝒮𝒞𝒯(G)=𝒮𝒞𝒯(G2). Hence,  𝒮𝒞𝒯(G)=min{𝒞𝒯t(G1)∪𝒞𝒯(G2),𝒮𝒞𝒯(G2)}.
Following the discussion above,  the statement is true.We can develop a dynamic programming algorithm to solve the weighted maximum-clique transversal set problem in linear time for distance-hereditary graphs as follows.Without loss of generality,  we assume thatG is a connected distance-hereditary graph with a vertex-weight function w. Given a PTF-tree PTF(G) of G rooted at node r,  our algorithm starts from the leaves of PTF(G) and works upward to the root. For each node ℓ of PTF(G),  let Tℓ be the subtree of PTF(G) rooted at node ℓ,  and let Gℓ represent the subgraph of G induced by the leaves of Tℓ. A node ℓ represents either a single-vertex subgraph of G or a subgraph Gℓ of G obtained by applying one of pendant vertex,  true twin,  or false twin operations to children of node ℓ. We use ℓ1 and ℓ2 to denote the left and right children of node ℓ,  respectively, if node ℓ is a nonleaf node of PTF(G). Therefore G=Gr and Gr is formed from Gr1 and Gr2. For each node ℓ,  our algorithm computes ω(Gℓ),  ωt(Gℓ),  𝒞𝒯(Gℓ),  𝒞𝒯t(Gℓ), and 𝒮𝒞𝒯(Gℓ),  in O(1) time by Lemmas 8.7–8.10. Then 𝒞𝒯(Gr) is a maximum-clique transversal set of G of minimum weight. Note that PTF(G) has 2n-1 tree nodes and can be constructed in linear time. Hence,  we obtain the following result.Theorem 8.11.
IfG is a weighted distance-hereditary graph,  then maximum-clique transversal set of G of minimum weight can be computed in linear time.


## 9. Conclusions

In this paper,  we have presented polynomial-time algorithms (most of them with linear running time) for the weighted maximum-clique transversal set problem on split graphs,  balanced graphs,  strongly chordal graphs,  Helly circular-arc graphs,  comparability graphs,  distance-hereditary graphs,  and graphs of bounded treewidth. For further study,  it is a great challenge to work on the complexity of this problem for other classes of graphs.



---

*Source: 540834-2012-01-26.xml*