Open AccessArticle

Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs

Chuan-Min Lee

Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan

Symmetry 2022, 14(4), 676; https://doi.org/10.3390/sym14040676

Submission received: 6 March 2022 / Revised: 19 March 2022 / Accepted: 23 March 2022 / Published: 24 March 2022

(This article belongs to the Special Issue Graph Algorithms and Graph Theory)

Download

Browse Figures

Versions Notes

Abstract

With the rapid growth in the penetration rate of mobile devices and the surge in demand for mobile data services, small cells and mobile backhaul networks have become the critical focus of next-generation mobile network development. Backhaul requirements within current wireless networks are almost asymmetrical, with most traffic flowing from the core to the handset, but 5G networks will require more symmetrical backhaul capability. The deployment of small cells and the placement of transceivers for cellular phones are crucial in trading off the symmetric backhaul capability and cost-effectiveness. The deployment of small cells is related to the placement of transceivers for cellular phones. Chang, Kloks, and Lee transformed the placement problem into the maximum-clique transversal problem on graphs. From the theoretical point of view, our paper considers the parameterized complexity of variations of the maximum-clique transversal problem for split graphs, doubly chordal graphs, planar graphs, and graphs of bounded treewidth.

Keywords:

parameterized complexity; asymmetric networks; signed maximum-clique transversal function; minus maximum-clique transversal function; symmetrical backhaul capability

1. Introduction

Fixed/mobile network convergence enhances the competitive advantage of telecommunications operators/companies. With the rapid growth in the penetration rate of mobile devices and the surge in demand for mobile data services, telecommunications operators are stepping up their pace to actively improve their wireless network infrastructure to cope with the advent of the mobile broadband networks era. They have to extend broadband networks to any place through the seamless connection between fixed and mobile networks, which helps accelerate the deployment time, reduces maintenance costs, and further enhances market competitiveness. Under the circumstances, small cells and mobile backhaul networks have become the critical focus of next-generation mobile network development.

The so-called mobile backhaul network transmits the mobile signal traffic between the base station and the mobile terminal device to the wireless node, and then aggregates and transmits it to the telecommunications core network. Backhaul requirements within current wireless networks are almost asymmetrical, with most traffic flowing from the core to the handset, but 5G networks will require more symmetrical backhaul capability. Furthermore, we must backhaul massive broadband traffic from small cells to the control center when small cells grow very large. Hence, the deployment of small cells and the placement of transceivers for cellular phones are crucial in trading off the symmetric backhaul capability and cost-effectiveness. The deployment of small cells is related to the placement of transceivers for cellular phones. Chang, Kloks, and Lee transformed the placement problem into the maximum-clique transversal problem on graphs [1]. One of their main objectives is as follows. Modern cellular telecommunications systems divide the entire service area into a set of small regions, which are called cells. Cells are generally thought of as hexagonal grids. One standard method used to place transceivers for cellular telephones is to place them at the corner points of each hexagonal grid. Since the need for communication proliferates, one transceiver cannot handle all communication requirements in its reach. The most widely used solution is to place another transceiver close to it. The system needs to assign a different frequency to this new transceiver to avoid interference. However, the number of available frequencies is limited. The rapidly increasing demand for communications makes the number of transceivers, placed close to each other, grow very large. It is desirable to replace them with a more efficient big transceiver tower. These towers are pretty large and rise hundreds of feet into the air. They contain very costly hardware to switch between different frequencies between transceivers in some optimal way to allocate and handle them with great care. Nevertheless, since transceiver towers are very costly, their number is expected to be as small as possible. The placement of transceivers for cellular telephones motivated Chang et al. to introduce the maximum-clique transversal problem on graphs [1]. Later, several studies have proposed and worked on variations of the maximum-clique transversal set problem from the theoretical point of view [2,3,4,5,6,7,8,9]. Most of them either develop algorithms to solve the problems and evaluate algorithms’ performance by asymptotic analysis (based on big O notation) to see if the algorithms can solve the problems in polynomial time or prove the NP-completeness of the problems for some graph classes. Their approaches are concerned with two classical computational complexity classes: P and NP.

This paper considers the parameterized complexity of the clique transversal problem (CTP) and variations of the maximum-clique transversal problem (MCTP) on graphs, such as the k-fold maximum-clique transversal problem (k-FMCTP), the

{k}

-maximum-clique transversal problem (

{k}

-MCTP), the signed maximum-clique trasversal problem (SMCTP), and the minus maximum-clique transversal problem (MMCTP).

Parameterized complexity is a new branch of computational complexity theory. Consider an algorithm for a parameterized problem

(I, k)

, where I is the problem instance and k the parameter. The algorithm is uniformly polynomial if it runs in

O (f (k) | I |^{c})

time, where

| I |

is the size of I,

f (k)

an arbitrary function, and c a constant independent of k. A parameterized problem is fixed-parameter tractable (FPT) if it admits a uniformly polynomial algorithm [10]. An fpt-reduction is a reduction transforming an instance of some parameterized problem into an equivalent instance of another parameterized problem and can be computed in uniformly polynomial time. A parameterized problem is para-NP-complete if it is NP-complete for fixed values of the parameter(s).

The W-hierarchy is another way to classify parameterized problems into computation complexity classes [10]. A parameterized problem is in the class

W [i]

if it is fpt-reducible to the circuit-satisfiability problem that has weft at most i [10]. If a problem

Q \in W [i]

and every problem in

W [i]

can be fpt-reduced to Q, problem Q is

W [i]

-complete. Note that

F P T = W [0]

and

W [i] \subseteq W [j]

for all

i < j

There are very few algorithmic results for the parameterized complexity of the CTP and variations of the MCTP. Table 1 lists previous results and our fixed parameter intractable results for the considered problems, and uses “

W [2]

-c” and “para-NP-c” to represent “

W [2]

-complete” and “para-NP-complete”, respectively. Table 2 lists previous results and our fixed parameter tractable results for the considered problems and uses n and

ω

to represent the number of vertices and the maximum size of a clique in a graph. Both tables use starred entries to denote our results. In Table 2, c is a moderate constant. As far as we know,

c = 4^{6 \sqrt{34}}

by the paper [11]. The rest of the paper is organized as follows.

Section 2 reviews the definitions of the considered problems and the most well-known notions from graph theory.
We prove in Section 3 that the clique transversal problem parameterized by the solution size is $W [2]$ -complete for split graphs, and the following problems are para-NP-complete: the minus maximum-clique transversal problem parameterized by the solution weight for planar graphs, and the signed maximum-clique transversal problem parameterized by the solution weight for doubly chordal graph and planar graphs with clique number three.
We show the FPT results for graphs of bounded treewidth in Section 4.
- Section 4.1 shows that the k-fold maximum-clique transversal problem can be solved in $O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)$ time for any graph G with bounded treewidth $t w (G)$ .
- Section 4.2 reduces the ${k}$ -maximum-clique transversal problem to the k-fold maximum-clique transversal problem and solves the problem in $O (2^{k (t w (G) + 1)} \cdot k^{2} \cdot (t w (G) + 1) \cdot | V (G) |)$ time. We develop a dynamic programming algorithm to improve the complexity of the problem to $O ({(k + 1)}^{t w (G) + 1} \cdot t w (G) \cdot | V (G) |)$ time.
- Section 4.3 deals with the signed and minus maximum-clique transversal problems. We reduce the signed and minus maximum-clique transversal problems to the k-fold maximum-clique transversal problem and solve these problems in $O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)$ and $O (4^{t w (G)} \cdot t w (G) \cdot | V (G) |)$ time, respectively. The complexity of the minus maximum-clique transversal problem for graphs of bounded treewidth can be improved to $O (3^{t w (G)} \cdot t w (G) \cdot | V (G) |)$ by our dynamic programming technique used for the ${k}$ -maximum-clique transversal problem.
Finally, we conclude the paper and present some future works in Section 5.

2. Definitions and Notations

All graphs in this paper are undirected graphs without self-loops and multiple edges. Let

G = (V, E)

be a graph with

| V | = n

and

| E | = m

. The vertex set of G is also referred to as

V (G)

and its edge set as

E (G)

. We use

u v

to denote the edge between the vertices u and v in a graph. If any two distinct vertices in a graph are adjacent, then the graph is a complete graph. We use

G [W]

to denote the subgraph of G induced by a subset W of V. The neighborhood of a vertex v in a graph G, denoted by

N_{G} (v)

, is the set of all v’s neighbors in G. The closed neighborhood of a vertex v in G, denoted by

N_{G} [v]

, is

N_{G} (v) \cup {v}

. The degree of a vertex v in G, denoted by

d e g_{G} (v)

, is the number of v’s neighbors in G. A dominating set of G is a set

D \subseteq V

such that

| D \cap N_{G} [v] | \geq 1

for every

v \in V

. The domination number of G, denoted by

γ (G)

, is the minimum cardinality of a dominating set of G. The domination problem is to find a minimum dominating set of G.

A set

S \subseteq V

is a clique if

x y \in E

for any two distinct vertices

x, y \in S

. If

| S | = k

, then S is a k-clique. If a clique C is not a proper subset of any other clique, then C is a maximal clique. A set

D \subseteq V

is a clique transversal set of G if

| C \cap D | \geq 1

for every maximal clique C 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 transversal problem is to find a clique transversal set of G of minimum cardinality.

A maximal clique S is a maximum clique if

| S | \geq | S^{'} |

for any maximal clique

S^{'}

of G. The clique number of G, denoted by

ω (G)

, is the cardinality of a maximum clique of G. We use

Q (G)

to denote the set of all maximum cliques of G. A set

D \subseteq V

is a maximum-clique transversal set of G if

| D \cap Q | \geq 1

for every

Q \in Q (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 problem is to find a maximum-clique transversal set of G of minimum cardinality.

Assume that

Y \subset R

and

f : S \to Y

is a function. Let

f (S^{'}) = \sum_{s \in S^{'}} f (s)

for

S^{'} \subseteq S

, and let

f (S)

be the weight of f. A maximum-clique transversal set of G can be expressed as a function f whose domain is

V (G)

and range is

{0, 1}

, and

f (Q) \geq 1

for

Q \in Q (G)

. The function f is a maximum-clique transversal function of G and

τ_{M} (G)

is the minimum weight of a maximum-clique transversal function of G. The k-fold maximum-clique,

{k}

-maximum-clique, minus maximum-clique, and signed maximum-clique transversal problems are variations of the maximum-clique transversal set problem. They are defined as follows.

Definition 1

([3]). Suppose that

k \in Z^{+}

is fixed and G is a graph. A set

D \subseteq V (G)

is a k-fold maximum-clique transversal set of G if

| Q \cap D | \geq k

for

Q \in Q (G)

. The number

τ_{\times k} (G) = m i n {| S | ∣ S

is a k-fold maximum-clique transversal set of

G}

is the k-fold maximum-clique transversal number of G. The k-fold maximum-clique transversal problem is to find a k-fold maximum-clique transversal set of G of minimum cardinality.

Definition 2

([3]). Suppose that

k \in Z^{+}

is fixed and G is a graph. A function f is a

{k}

-maximum-clique transversal function of G if the domain and range of f are

V (G)

and

{0, 1, 2, \dots, k}

, respectively, and

f (Q) \geq k

for

Q \in Q (G)

. The number

τ_{{k}} (G) = m i n {f (V (G)) ∣ f

is a

{k}

-maximum-clique transversal function of

G}

is the

{k}

-maximum-clique transversal number of G. The

{k}

-maximum-clique transversal problem is to find a

{k}

-maximum-clique transversal function of G of minimum weight.

Definition 3

([3]). Suppose that G is a graph. A function f is a signed maximum-clique transversal function of G if the domain and range of f are

V (G)

and

{- 1, 1}

, respectively, and

f (Q) \geq 1

for

Q \in Q (G)

. If the domain and range of f are

V (G)

and

{- 1, 0, 1}

, respectively, and

f (Q) \geq 1

for

Q \in Q (G)

, then f is a minus maximum-clique transversal function of G. The number

τ_{M}^{s} (G) = m i n {f (V (G)) ∣ f

is a signed maximum-clique transversal function of

G}

is the signed maximum-clique transversal number of G. The minus maximum-clique transversal number of G is

τ_{M}^{-} (G) = m i n {f (V (G)) ∣ f

is a minus maximum-clique transversal function of

G}

. The minus (signed) maximum-clique transversal problem is to find a minus (signed) maximum-clique transversal function of G of minimum weight.

3. The Fixed-Parameter Intractable Results

A chord of a cycle is an edge joining two non-consecutive vertices of the cycle. A graph is chordal if it does not contain a chordless cycle of length greater than three [12]. A graph is split if its vertices can be partitioned into two sets C and S, such that C is a clique and S is an independent set.

Theorem 1.

The clique transversal problem parameterized by the solution size is

W [2]

-complete for split graphs.

Proof.

Assume that

G = (V, E)

is a graph with

V = {v_{i} ∣ 1 \leq i \leq n}

. Let

X = {x_{i} ∣ 1 \leq i \leq n}

and let H be a split graph obtained from G by

V (H) = V \cup X

and

E (H) = {v_{i} v_{j} ∣ 1 \leq i < j \leq n} \cup {x_{i} v | v \in N_{G} [v_{i}], 1 \leq i \leq n}

. In H, the maximal cliques are the sets V and

N_{G} [v_{i}] \cup {x_{i}}

for

1 \leq i \leq n

. A minimum dominating set of G is a clique transversal set of H. Clearly, there exists a minimum clique transversal set D of H such that

D \cap X = \emptyset

. Then, a minimum clique transversal set of H is a dominating set of G. We have

γ (G) = τ_{C} (H)

following the discussion above. Hence,

τ_{C} (H) \leq k

if, and only if,

γ (G) \leq k

. The domination problem for a graph G can be reduced to the clique transversal problem for a split graph H. Since the domination problem parameterized by the solution size k is

W [2]

-complete [10], the clique transversal problem parameterized by the solution size is

W [2]

-complete for split graphs. □

Remark 1.

The maximum-clique transversal is a particular case of the k-fold maximum-clique transversal problem with

k = 1

. The k-fold maximum-clique,

{k}

-maximum-clique, minus maximum-clique, and signed maximum-clique transversal problems are linear-time solvable for split graphs [3].

Consider the following two decision problems.

The nonpositive minus maximum-clique transversal problem.
Instance: A graph G
Question: Does G have a minus maximum-clique transversal function of weight at most 0?
The nonpositive signed maximum-clique transversal problem.
Instance: A graph G
Question: Does G have a signed maximum-clique transversal function of weight at most 0?

Definition 4.

Let k be a nonnegative integer and let F be a set of k vertices. The

f_{k}

-transformation of a graph

G = (V, E)

, denoted by

f_{k} (G)

, is the graph

H = (V \cup F, E)

Theorem 2.

Let

G

and

H

be graph classes such that

H = {f_{k} (G) ∣ G \in G}

. The following statements are true.

(1): If the signed (minus) maximum-clique transversal problem is NP-complete for $G$ , the nonpositive signed (minus) maximum-clique transversal problem is NP-complete for $H$ .
(2): If the nonpositve signed (minus) maximum-clique transversal problem is NP-complete for graph class $H$ , the signed (minus) maximum-clique transversal problem parameterized by the solution weight is para-NP-complete for $H$ .

Proof.

(1) Let k be a nonnegative integer and let F be a set of k vertices. Let

G = (V, E) \in G

and

H = (V \cup F, E) \in H

. In H, every vertex

x \in F

is isolated and not in any maximum clique of H. Then,

f (x) = - 1

for any signed (minus) maximum-clique transversal function f of H of “minimum weight”. Clearly,

τ_{M}^{s} (H) = τ_{M}^{s} (G) - | F | = τ_{M}^{s} (G) - k

. It follows that

τ_{M}^{s} (H) \leq 0

if and only if

τ_{M}^{s} (G) \leq k

. Similarly,

τ_{M}^{-} (H) = τ_{M}^{-} (G) - | F | = τ_{M}^{-} (G) - k

. Then,

τ_{M}^{-} (H) \leq 0

if and only if

τ_{M}^{-} (G) \leq k

. The statement (1) is therefore true.

(2) The nonpositive signed (minus) maximum-clique transversal problem for

H

is a particular case of the signed (minus) maximum-clique transversal problem parameterized by solution weight for

H

. Hence, the statement (2) is true. □

Corollary 1.

Let

G_{1}

be the graph class of planar graphs and let

G_{2}

be the graph class of doubly chordal graphs and planar graphs with the clique number 3. The following statements are true.

(1): The nonpositive minus maximum-clique transversal problem is NP-complete for $G_{1}$ .
(2): The nonpositive signed maximum-clique transversal problem is NP-complete for $G_{2}$ .

Proof.

(1) Let

G \in G_{1}

and

H = f_{k} (G)

. Clearly,

H \in G_{1}

. It is known that the minus maximum-clique transversal problem is NP-complete for

G_{1}

[3]. By Theorem 2, the nonpositive minus maximum-clique transversal problem is NP-complete for

G_{1}

(2) Let

G \in G_{2}

and

H = f_{k} (G)

. Clearly,

H \in G_{2}

. It is known that the signed maximum-clique transversal problem is NP-complete for

G_{2}

[3]. By Theorem 2, the nonpositive signed maximum-clique transversal problem is NP-complete for

G_{2}

. □

Corollary 2.

Let

G_{1}

be the graph class of planar graphs and let

G_{2}

be the graph class of doubly chordal graphs and planar graphs with the clique number 3. The following statements are true.

(1): The minus maximum-clique transversal problem parameterized by the solution weight is para-NP-complete for $G_{1}$ .
(2): The signed maximum-clique transversal problem parameterized by the solution weight is para-NP-complete for $G_{2}$ .

Proof.

The corollary holds by Theorem 2 and Corollary 1. □

4. Fixed-Parameter Tractable Results for Graphs of Bounded Treewidth

Assume that G is a graph with

V (G) = {v_{1}, v_{2}, \dots, v_{n}}

. Let

N_{i} [v]

denote the closed neighborhood of v in

G [{v_{i}, v_{i + 1}, \dots, v_{n}}]

. The ordering

(v_{1}, v_{2}, \dots, v_{n})

of V is a perfect elimination ordering of G if for all

i \in {1, \dots, n}

N_{i} [v_{i}]

is a clique. A graph G is chordal if and only if G has a perfect elimination ordering [13].

A chordal graph H with n vertices is a t-tree if and only if either H is a complete graph of t vertices or H has more than t vertices and there exists a perfect elimination ordering

(v_{1}, v_{2}, \dots, v_{n})

such that

N_{i} [v_{i}]

is a

(t + 1)

-clique for

1 \leq i \leq n - t

. For convenience, we define a t-tree to have at least

t + 1

vertices. With this definition, a complete graph of t vertices is a

(t - 1)

-tree.

A triangulation of a graph G is a graph H with the same set of vertices such that H is chordal and G is a subgraph of H. We say that G is triangulated into H. Subgraphs of t-trees are called partial t-trees. The treewidth of a graph G is the minimum value t such that G is a partial t-tree. It is clear that a graph of treewidth t is also a partial ℓ-tree for every

ℓ \geq t

. The class of partial t-trees is exactly the class of graphs of treewidth at most t. Therefore,

ω (G) = t + 1

for any graph G of treewidth t. The treewidth of a graph can be defined by the concept of tree decomposition of a graph.

Definition 5.

A tree decomposition of a graph G is a pair

D = (T, B)

, where T is a tree with

V (T) = {1, 2, \dots, ℓ}

and

B = {B_{i} ∣ i \in V (T)}

is a collection of subsets of vertices of G such that the following three conditions are satisfied.

1.: Every vertex $x \in V (G)$ appears in at least one set $B_{i} \in B$ .
2.: For every edge $e \in E (G)$ , there is at least one set $B_{i} \in B$ containing both vertices of e.
3.: For each vertex $x \in V (G)$ , the set ${i ∣ x \in B_{i}}$ forms a subtree of T.

For simplicity, we use T to represent the vertex set of T if T is understood as a tree and we call its vertices nodes. We also refer to all elements of B as bags. Lemma 1 shows an alternative way to formulate the third condition of Definition 5.

Lemma 1.

Let

D = (T, {B_{i} ∣ i \in T})

be a tree decomposition of a graph G. If a vertex x appears in two bags

B_{i}, B_{j} \in B

, then it appears in every bag

B_{k}

for the node k on the tree path from node i to node j in T.

Definition 6.

The width of a tree decomposition

D = (T, {B_{i} ∣ i \in T})

of a graph G is

{max}_{i \in T} {| B_{i} |} - 1

. The treewidth of a graph G, denoted by

t w (G)

, is the minimum width over all tree decompositions of G.

Theorem 3

(See also Lemma 2.1.13 in [14]). If G is a chordal graph with at least

t + 1

vertices and

ω (G) \leq t + 1

, then G can be triangulated into a t-tree.

Theorem 4

([15]). Any partial t-tree with at least

t + 1

vertices can be triangulated into a t-tree with the same number of vertices.

Definition 7.

A tree decomposition is rooted if the tree is equipped with a root node. A nice tree decomposition

D = (T, {B_{i} ∣ i \in T})

is a rooted tree decomposition satisfying the following conditions.

1.: Every node of T has at most two child nodes.
2.: If a node i has two child nodes—j and k—then $B_{i} = B_{j} = B_{k}$ . The node is called a join node.
3.: If a node i has only one child node j, then either (1) $B_{j} \subset B_{i}$ and $| B_{i} | = | B_{j} | + 1$ , or (2) $B_{i} \subset B_{j}$ and $| B_{i} | = | B_{j} | - 1$ . In the case (1), the node is called an introduce node, whereas in the case (2), the node is called a forget node.

Remark 2.

Figure 1 shows a nice tree decomposition

D = (T, {B_{i} ∣ i \in T})

of a graph G, where T has 17 nodes. Node 3 is a join node since it has two child nodes, 4 and 9, and

B_{3} = B_{4} = B_{9} = {b, c, d}

. Node 6 is an introduce node since it has only one child node 7, and

B_{7} \subset B_{6}

and

| B_{6} | = | B_{7} | + 1

. Node 10 is a forget node since it has only one child node 11, and

B_{10} \subset B_{11}

and

| B_{10} | = | B_{11} | - 1

Lemma 2

([14]). For any constant t, given a tree decomposition of a graph G of width t and

O (| V (G) |)

nodes, one can find a nice tree decomposition of G of width t and with at most

4 \cdot | V (G) |

nodes in

O (| V (G) |)

time.

This paper assumes that a nice tree decomposition of a graph G of width

t w (G)

and with

O (| V (G) |)

nodes is part of the input by Lemma 2.

4.1. The k-Fold Maximum-Clique Transversal Problem

This section studies the k-fold maximum-clique transversal problem on graphs of bounded treewidth.

Definition 8.

Let

D = (T, {B_{i} ∣ i \in T})

be a rooted tree decomposition of G. For each node

i \in T

, let

T_{i}

be the subtree of T rooted at i and and let

G_{i}

be the induced subgraph

G [\cup_{s \in T_{i}} B_{s}]

. Clearly,

T = T_{r}

and

G = G_{r}

Theorem 5

([16]). Assume that

D = (T, B)

is a tree decomposition of a graph G. For every clique C of G, there exists a bag

B_{p} \in B

such that

C \subseteq B_{p}

Lemma 3.

Let

D = (T, B)

be a tree decomposition of a graph G of width

t w (G)

. For each maximum clique Q of G, there exists a bag

B_{p} \in B

such that

Q = B_{p}

Proof.

Following Theorem 5, there exists a bag

B_{p} \in B

such that

Q \subseteq B_{p}

for a maximum clique Q of G. Then,

| Q | \leq | B_{p} |

. Clearly,

| B_{p} | \leq t w (G) + 1 \leq ω (G) = | Q |

. Hence,

Q = B_{p}

. □

Definition 9.

Let G be a graph of bounded treewidth with a nice tree decomposition

(T, {B_{i} ∣ i \in T})

rooted at node r. Let k be a fixed positive integer such that

k \leq ω (G)

. For each node

i \in T

, let

F_{k, i} (X)

be a minimum subset S of

V (G_{i})

satisfying all the following conditions.

(1): $S \cap B_{i} = X$ .
(2): $| S \cap Q | \geq k$ for every maximum clique $Q \in Q (G_{i}) \cap Q (G)$ .

F_{k, i} (X)

does not exist, let

F_{k, i} (X) = Φ

with

| Φ | = \infty

Remark 3.

By Definition 9,

T = T_{r}

G = G_{r}

, and

τ_{\times k} (G) = min {| F_{k, r} (X) | ∣ X \subseteq B_{r}}

Lemma 4.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is a leaf node of T. Then, all sets

F_{k, i} (X)

G_{i}

can be computed in

O (2^{t w (G)} \cdot t w (G))

time.

Proof.

Since node i is a leaf node,

G_{i} = G [B_{i}]

and

Q (G_{i}) \cap Q (G) = Q (G [B_{i}])

. By the definition of tree decomposition,

| B_{i} | \leq t w (G) + 1

and

ω (G) = t w (G) + 1

. If

B_{i}

is not a maximum clique of G, then

F_{k, i} (X) = Φ

for

X \subseteq B_{i}

. It takes

O (t w {(G)}^{2})

time to check if

B_{i}

is a maximum clique. We therefore assume that

B_{i}

is a maximum clique of G. Note that

F_{k, i} (X) = X \subseteq B_{i}

in this case. There are

O (2^{t w (G)})

subsets of

B_{i}

. For each

F_{k, i} (X)

B_{i}

, we verify if

F_{k, i} (X)

has at least k vertices in

B_{i}

. The verification process can be done in

O (t w (G))

time. Following the discussion above, all sets

F_{k, i} (X)

G_{i}

can be computed in

O (2^{t w (G)} \cdot t w (G))

time. □

Lemma 5.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is a forget node of T. Let j be the child node of i and let

x \in B_{j}

be the vertex such that

B_{i} = B_{j} \ {x}

. Let

X \subseteq B_{j}

such that

s_{1} = | F_{k, j} (X) |

and

s_{2} = | F_{k, j} (X \cup {x}) |

. Then,

F_{k, i} (X) = \{\begin{matrix} F_{k, j} (X) & i f s_{1} \leq s_{2}, \\ F_{k, j} (X \cup {x}) & i f s_{2} < s_{1} . \end{matrix}

Proof.

Since

B_{i} = B_{j} \ {x}

G_{i} = G_{j}

. Then,

X = F_{k, i} (X) \cap B_{i} = F_{k, i} (X) \cap (B_{j} \ {x})

. Therefore, either

F_{k, i} (X) \cap B_{j} = X

F_{k, i} (X) \cap B_{j} = X \cup {x}

. We have

| F_{k, i} (X) | = min {| F_{k, j} (X) |, | F_{k, j} (X \cup {x} |}

. Hence, the lemma holds. □

Lemma 6.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is an introduce node of T. Let j be the child node of i and let x be the vertex such that

B_{i} = B_{j} \cup {x}

. For

X \subseteq B_{i}

F_{k, i} (X) = \{\begin{matrix} F_{k, j} (X) & i f B_{i} \notin Q (G) a n d x \notin X, \\ F_{k, j} (X \ {x}) \cup {x} & i f B_{i} \notin Q (G) a n d x \in X, \\ F_{k, j} (X) & i f B_{i} \in Q (G), x \notin X, a n d | X | \geq k, \\ F_{k, j} (X \ {x}) \cup {x} & i f B_{i} \in Q (G), x \in X, a n d | X | \geq k, \\ Φ & o t h e r w i s e . \end{matrix}

Proof.

Let d be a proper descendant of the subtree

T_{j}

. Since

x \notin B_{j}

x \notin V (G_{j})

, by the third condition of Definition 5. Then,

x \notin B_{d}

. We consider the following two cases.

Case 1:

B_{i} \notin Q (G)

. Assume that there exists a set

S \subseteq B_{d}

such that

S \cup {x}

is a maximum clique of G. By Lemmma 3, there exists a bag

B_{p}

such that

S \cup {x} = B_{p}

. Since

B_{p}

contains the vertex x, the corresponding node p is not in

T_{j}

. Then, every tree path from node d to node p contains the nodes i and j. By Lemma 1,

S = B_{j} = B_{i} \ {x}

. Then,

B_{i} = S \cup {x}

is a maximum clique of G, but it contradicts that

B_{i} \notin Q (G)

. Therefore, there is no set

S \subseteq B_{d}

such that

S \cup {x} \in Q (G)

. We have

Q (G_{i}) \cap Q (G) = (Q (G_{j}) \cap Q (G))

. Then,

F_{k, i} (X) = F_{k, j} (X)

x \notin X

. Otherwise,

F_{k, i} (X) = F_{k, j} (X \ {x}) \cup {x}

Case 2:

B_{i} \in Q (G)

. Assume that there exists a set

S \subseteq B_{d}

such that

S \cup {x} \in Q (G)

. By the arguments similar to those for proving Case 1,

B_{i} = S \cup {x}

. Therefore,

Q (G_{i}) \cap Q (G) = (Q (G_{j}) \cap Q (G)) \cup {B_{i}}

. Conversely, we assume that there is no set

S \subseteq B_{d}

such that

S \cup {x} \in Q (G)

. Clearly,

Q (G_{i}) \cap Q (G) = (Q (G_{j}) \cap Q (G)) \cup {B_{i}}

. Since

X \subseteq B_{i}

| X | \geq k

. If

| X | < k

, then

F_{k, i} (X)

does not exist. Therefore,

F_{k, i} (X) = F_{k, j} (X)

x \notin X

and

| X | \geq k

. If

x \in X

and

| X | \geq k

, then

F_{k, i} (X) = F_{k, j} (X \ {x}) \cup {x}

. □

Remark 4.

The method used for proving Lemma 6 is similar to the one adopted in estimating Roman domination [17].

Lemma 7.

Let G be a graph of bounded treewidth with a nice tree decomposition

(T, {B_{i} ∣ i \in T})

. Suppose that node i is a join node of T. Let j and ℓ be the child nodes of i. For

X \subseteq B_{i}

F_{k, i} (X) = F_{k, j} (X) \cup F_{k, ℓ} (X) .

Proof.

Since node i is a join node,

B_{i} = B_{j} = B_{ℓ}

. Then,

Q (G_{i}) = Q (G_{j}) \cup Q (G_{ℓ})

. Let

S = F_{k, j} (X) \cup F_{k, ℓ} (X)

. Clearly,

S \cap B_{i} = X

and

| S \cap Q | \geq k

for

Q \in Q (G_{i}) \cap Q (G)

. We have

| F_{k, i} (X) | \leq | S | = | F_{k, j} (X) \cup F_{k, ℓ} (X) |

Let

S_{1} = F_{k, i} (X) \cap V (G_{j})

and

S_{2} = F_{k, i} \cap V (G_{ℓ})

. Since X is a subset of

S_{1} \cup S_{2}

| F_{k, i} (X) | = | (S_{1} \cup X) \cup (S_{2} \cup X) |

. Let

S_{j} = S_{1} \cup X

and

S_{ℓ} = S_{2} \cup X

. Clearly,

S_{j} \cap B_{j} = X

and

S_{ℓ} \cap B_{ℓ} = X

. Futhermore,

| S_{j} \cap Q | \geq k

for

Q \in Q (G_{j}) \cap Q (G)

and

| S_{ℓ} \cap Q | \geq k

for

Q \in Q (G_{ℓ}) \cap Q (G)

. Therefore,

| F_{k, j} (X) | \leq | S_{j} |

and

| F_{k, ℓ} (X) | \leq | S_{ℓ} |

. We have

| F_{k, j} (X) \cup F_{k, ℓ} (X) | \leq | S_{j} \cup S_{ℓ} | = | F_{k, i} (X) |

. Following the discussion above,

| F_{k, i} (X) | = | F_{k, j} (X) \cup F_{k, ℓ} (X) |

and the lemma holds. □

Theorem 6.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

and

O (| V (G) |)

nodes. The k-fold maximum-clique transversal problem can be solved in

O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time.

Proof.

Assume that T is rooted at r. Then,

T = T_{r}

G = G_{r}

, and

τ_{\times k} (G) = min {| F_{k, r} (X) | ∣ X \subseteq B_{r}}

. Our algorithm works from the leaves in T up to the root, computing the solutions

F_{i} (X)

for each visited node i on the way through the dynamic programming technique. For all

X \in B_{i}

, the solutions can be computed in

O (2^{t w (G)} \cdot t w (G))

time by Lemmas 4–7. Since T contains

O (| V (G) |)

nodes, the k-fold maximum-clique transversal problem can be solved in

O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time. □

4.2. The ${k}$ -Maximum-Clique Transversal Problem

This section studies the

{k}

-maximum-clique transversal problem on graphs of bounded treewidth and solves the problem with reduction and the dynamic programming technique.

4.2.1. Problem Solving by Reduction

The section shows a reduction from the

{k}

-maximum-clique transversal problem to the k-fold maximum-clique transversal problem by the concept of the strong product of two graphs.

Definition 10.

The strong product

G ⊠ H

is defined on the vertex set

V (G) \times V (H)

, where two vertices

(u_{1}, v_{1})

and

(u_{2}, v_{2})

are adjacent if and only if

u_{1} = u_{2}

and

v_{1} v_{2} \in E (H)

, or

v_{1} = v_{2}

and

u_{1} u_{2} \in E (G)

, or

v_{1} v_{2} \in E (H)

and

u_{1} u_{2} \in E (G)

Figure 2 shows the strong product of a graph G and a complete graph H. The graph

G ⊠ H

, as shown in Figure 2c, consists of twelve vertices. From left to right, the vertices in row i are

(u_{i}, v_{1})

(u_{i}, v_{2})

, and

(u_{i}, v_{3})

for

i \in {1, 2, 3, 4}

Lemma 8.

Let G and H be graphs. Then,

Q (G ⊠ H) = {V (G [Q_{1}] ⊠ H [Q_{2}]) ∣ Q_{1} \in Q (G), Q_{2} \in Q (H)}

Proof.

Let

Q_{1} \in Q (G)

and

Q_{2} \in Q (H)

. The vertex set,

V (G [Q_{1}] ⊠ H [Q_{2}])

, is a clique of

G ⊠ H

. We have

ω (G) \cdot ω (H) \leq ω (G ⊠ H)

Let

V (G) = {u_{1}, \dots, u_{n}}

and

V (H) = {v_{1}, \dots, v_{k}}

. Let

Q \in Q (G ⊠ H)

. For any two distinct vertices

(u_{p}, v_{x}), (u_{q}, v_{y}) \in Q

, (1)

u_{p} = u_{q}

and

v_{x} v_{y} \in E (H)

, or (2)

u_{p} u_{q} \in E (G)

and

v_{x} = v_{y}

, or (3)

u_{p} u_{q} \in E (G)

and

v_{x} v_{y} \in E (H)

. Therefore,

u_{p} u_{q} \in E (G)

u_{p} \neq u_{q}

for any two distinct vertices

(u_{p}, v_{x}), (u_{q}, v_{y}) \in Q

. Similarly,

v_{x} v_{y} \in E (H)

v_{x} \neq v_{y}

for any two distinct vertices

(u_{p}, v_{x}), (u_{q}, v_{y}) \in Q

, Then,

C_{1} = {u_{i} ∣ (u_{i}, v_{j}) \in Q, 1 \leq i \leq n, 1 \leq j \leq k}

is a clique of G and

C_{2} = {v_{j} ∣ (u_{i}, v_{j}) \in Q, 1 \leq i \leq n, 1 \leq j \leq k}

is a clique of H. Let

Q_{1} \in Q (G)

and

Q_{2} \in Q (H)

such that

C_{1} \subseteq Q_{1}

and

C_{2} \subseteq Q_{2}

. Hence,

Q \subseteq V (G [C_{1}] ⊠ H [C_{2}]) \subseteq V (G [Q_{1}] ⊠ H [Q_{2}])

. We have

ω (G ⊠ H) \leq ω (G) \cdot ω (H)

. Therefore,

ω (G ⊠ H) = ω (G) \cdot ω (H)

by the discussion above, and the lemma holds. □

Theorem 7.

Let k be a fixed positive integer and let H be a complete graph with k vertices. For any graph G and

k \geq 1

τ_{{k}} (G) = τ_{\times k} (G ⊠ H)

Proof.

Let

V (G) = {u_{1}, \dots, u_{n}}

and

V (H) = {v_{1}, \dots, v_{k}}

. By Lemma 8,

Q (G ⊠ H) = {V (G [Q] ⊠ H) ∣ Q \in Q (G)}

. Clearly,

| Q (G ⊠ H) | = | Q (G) |

and

ω (G ⊠ H) = k \cdot ω (G)

Let f a

{k}

-maximum-clique transversal function of G of minimum weight. Let D be a subset of

V (G ⊠ H)

defined by

D = ⋃_{i = 1}^{n} {(u_{i}, v_{j}) ∣ j = 1, 2, \dots, f (u_{i})} .

Since f is a

{k}

-maximum-clique transversal function,

0 \leq f (u_{i}) \leq k

for

1 \leq i \leq n

. Indeed, the set D exists, and

| D | = \sum_{i = 1}^{n} f (u_{i}) = τ_{{k}} (G)

. Let

C = {u_{b_{i}} ∣ 1 \leq i \leq ω (G)}

be a maximum clique of G such that

V (G [C] ⊠ H) = {(u_{b_{i}}, v_{j}) ∣ 1 \leq i \leq ω (G), 1 \leq j \leq k}

is a maximum clique of

G ⊠ H

. Since

f (C) = \sum_{i = 1}^{ω (G)} f (u_{b_{i}}) \geq k

| D \cap V (G [C] ⊠ H) | = | {(u_{b_{i}}, v_{j}) ∣ 1 \leq i \leq ω (G), 1 \leq j \leq f (u_{b_{i}})} | = \sum_{i = 1}^{ω (G)} f (u_{b_{i}}) \geq k .

The set D is a k-fold maximum-clique transversal set of

G ⊠ H

. We have

τ_{\times k} (G ⊠ H) \leq τ_{{k}} (G)

In the following, we show that

τ_{{k}} (G) \leq τ_{\times k} (G ⊠ H)

. Let S be a k-fold maximum-clique transversal set of

G ⊠ H

such that

| S | = τ_{\times k} (G ⊠ H)

Let

f : V (G) \to {0, 1, \dots, k}

be a function of G such that

f (u_{i}) = | S \cap {(u_{i}, v_{j}) ∣ j = 1, \dots, k} |

for

1 \leq i \leq n

. Clearly,

f (V (G)) = τ_{\times k} (G ⊠ H)

and

0 \leq f (u_{i}) \leq k

for

1 \leq i \leq n

. Recall that

Q (G ⊠ H) = {V (G [C] ⊠ H) ∣ C \in Q (G)}

. Let

C = {u_{b_{i}} ∣ 1 \leq i \leq ω (G)}

be a maximum clique of G such that

Q = V (G [C] ⊠ H)

is a maximum clique of

G ⊠ H

. Then,

Q = {(u_{b_{i}}, v_{j}) ∣ 1 \leq i \leq ω (G), 1 \leq j \leq k}

Since S is a k-fold maximum-clique transversal set of

G ⊠ H

| S \cap Q | = | S \cap {(u_{b_{i}}, v_{j}) ∣ 1 \leq i \leq ω (G), 1 \leq j \leq k} | \geq k

. Therefore,

f (C) = \sum_{i = 1}^{ω (G)} f (u_{b_{i}}) = \sum_{i = 1}^{ω (G)} | S \cap {(u_{b_{i}}, v_{j}) ∣ 1 \leq j \leq k} | = | S \cap Q | \geq k .

The function f is a

{k}

-maximum-clique transversal function of G. We have

τ_{{k}} (G) \leq f (V (G)) = τ_{\times k} (G ⊠ H)

. Hence,

τ_{{k}} (G) = τ_{\times k} (G ⊠ H)

by the discussion above. □

Lemma 9.

Let k be a fixed positive integer and let H be a complete graph with k vertices. Given a nice tree decomposition

D = (T, B = {B_{i} ∣ i \in T})

of a graph G of width

t w (G)

and

O (| V (G) |)

nodes, one can find a nice tree decomposition of

G ⊠ H

of width

k (t w (G) + 1) - 1

and with at most

4 \cdot | V (G ⊠ H) |

nodes in

O (| V (G ⊠ H) |)

time.

Proof.

Let

V (G) = {u_{i} ∣ 1 \leq i \leq n}

and

V (H) = {v_{i} ∣ 1 \leq i \leq k}

. Let

B_{i}^{'} = {(u_{ℓ}, v_{j}) | u_{ℓ} \in B_{i}, 1 \leq j \leq k}

and

D^{'} = (T, B^{'} = {B_{i}^{'} ∣ i \in T})

. We show as follows that

D^{'}

is a tree decomposition of

G ⊠ H

(1): Every vertex $u_{ℓ} \in V (G)$ appears in at least one bag of B. Suppose that $u_{ℓ} \in B_{i}$ . The vertices $(u_{ℓ}, v_{1})$ , $(u_{ℓ}, v_{2}), \dots, (u_{ℓ}, v_{k})$ all appear in $B_{i}^{'} \in B^{'}$ . Therefore, every vertex $(u_{ℓ}, v_{j}) \in V (G ⊠ H)$ appears in at least one bag $B_{i}^{'} \in B^{'}$ .
(2): For any two adjacent vertices $(u_{x}, v_{p}), (u_{y}, v_{q}) \in V (G ⊠ H)$ , $u_{x} = u_{y}$ and $v_{p} v_{q} \in E (H)$ , or $u_{x} u_{y} \in E (G)$ and $v_{p} = v_{q}$ , or $u_{x} u_{y} \in E (G)$ and $v_{p} v_{q} \in E (H)$ . Consider $u_{x}$ and $u_{y}$ . Either $u_{x} = u_{y}$ or $u_{x} u_{y} \in E (G)$ . If $u_{x} = u_{y}$ , then $u_{x}$ and $u_{y}$ are in the same bags. Suppose that $u_{x} \neq u_{y}$ and $u_{x} u_{y} \in E (G)$ . Since there is at least one bag of B containing both vertices of e for every edge $e \in E (G)$ , at least one bag contains the vertices $u_{x}$ and $u_{y}$ . Let $u_{x}, u_{y} \in B_{i}$ . The vertices $(u_{x}, v_{1})$ , $(u_{x}, v_{2}), \dots, (u_{x}, v_{k})$ and $(u_{y}, v_{1})$ , $(u_{y}, v_{2}), \dots, (u_{y}, v_{k})$ are in $B_{i}^{'} \in B^{'}$ . The bag $B_{i}^{'}$ contains $(u_{x}, v_{p})$ and $(u_{y}, v_{q})$ . Therefore, there is at least one bag of $B^{'}$ containing every pair of adjacent vertices of $G ⊠ H$ .
(3): Suppose that $(u_{ℓ}, v_{j})$ is a vertex of $G ⊠ H$ and it appears in two bags $B_{i}^{'}, B_{p}^{'} \in B^{'}$ . Let j be a node on the tree path from node i to node p in T. Since $(u_{ℓ}, v_{j})$ appears in $B_{i}^{'}$ and $B_{p}^{'}$ , we know that $u_{ℓ} \in B_{i}$ and $u_{ℓ} \in B_{p}$ . Then, $u_{ℓ} \in B_{j}$ by Lemma 1. The vertices $(u_{ℓ}, v_{1})$ , $(u_{ℓ}, v_{2}), \dots, (u_{ℓ}, v_{k})$ are in $B_{j}^{'}$ . Clearly, $(u_{ℓ}, v_{j}) \in B_{j}^{'}$ . Hence, a vertex $(u_{ℓ}, v_{j})$ appears in every bag $B_{j}^{'}$ for the node j on the tree path from node i to node p in T if it appears in $B_{i}^{'}, B_{j}^{'} \in B^{'}$ .

Following the discussion above,

D^{'} = (T, B^{'})

is a tree decomposition of

G ⊠ H

of width

k (t w (G) + 1) - 1

and with

O (| V (G) |)

nodes. By Lemma 2, we can obtain a nice tree decomposition of

G ⊠ H

of width

k (t w (G) + 1) - 1

with at most

4 \cdot | V (G ⊠ H) |

nodes in

O (| V (G ⊠ H))

time. □

Theorem 8.

Let G be a graph of bounded treewidth. Given a nice tree decomposition

D = (T, B = {B_{i} ∣ i \in T})

of G of width

t w (G)

and

O (| V (G) |)

nodes, the

{k}

-maximum-clique transversal problem can be solved in

O (2^{k (t w (G) + 1)} \cdot k^{2} \cdot (t w (G) + 1) | V (G) |)

time.

Proof.

Let H be a complete graph of k vertices. By Lemma 9, we can obtain a nice tree decomposition of

G ⊠ H

of width

k (t w (G) + 1) - 1

with at most

4 \cdot | V (G ⊠ H)

nodes in

O (| V (G ⊠ H) |)

time. Since k is fixed and G is a graph of bounded treewidth,

G ⊠ H

is a graph of bounded treewidth

k (t w (G) + 1) - 1

. Note that

| V (G ⊠ H) | = k \cdot | V (G) |

. By Theorems 6 and 7, the

{k}

-maximum-clique transversal problem can be solved in

O (2^{k (t w (G) + 1)} \cdot k^{2} \cdot (t w (G) + 1) | V (G) |)

time. □

4.2.2. Problem Solving by Dynamic Programming

This section studies the

{k}

-maximum-clique transversal problem by the dynamic programming technique for graphs of bounded treewidth.

Definition 11.

Assume that G is a graph and k is a positive integer. Let

X = (X_{0}, X_{1}, \dots, X_{k})

be a

(k + 1)

-tuple of subsets of

V (G)

. The weight of the

(k + 1)

-tuple X, denoted by

w (X)

, is

\sum_{i = 0}^{k} (| X_{i} | \cdot i)

. Let

ℓ \in {0, 1, \dots, k}

and let

V^{'} \subseteq V (G)

. Let

Y = (Y_{0}, Y_{1}, \dots, Y_{k})

be another

(k + 1)

-tuple of subsets of

V (G)

. We give the following notations and definitions.

1.

X \oplus Y

denotes the

(k + 1)

-tuple

(X_{0} \cup Y_{0}, \dots, X_{k} \cup Y_{k})

2.

X \oplus V^{'}

denotes the

(k + 1)

-tuple

(X_{0} \cup V^{'}, \dots, X_{k} \cup V^{'})

3.

X \oplus_{ℓ} V^{'}

denotes the

(k + 1)

-tuple

(S_{0}, \dots, S_{k})

such that

S_{ℓ} = X_{ℓ} \cup V^{'}

and

S_{i} = X_{i}

for

i \in {0, 1, \dots, k} \ {ℓ}

4.

X \otimes V^{'}

denotes the

(k + 1)

-tuple

(X_{0} \cap V^{'}, \dots, X_{k} \cap V^{'})

5.

X ⊖_{ℓ} V^{'}

denotes the

(k + 1)

-tuple

(S_{0}, \dots, S_{k})

such that

S_{ℓ} = X_{ℓ} \ V^{'}

and

S_{i} = X_{i}

for

i \in {0, 1, \dots, k} \ {ℓ}

6.

(k + 1)

-tuple

S = (S_{0}, \dots, S_{k})

is a

(k + 1)

-partition of

V (G)

satisfying the following conditions.

(a): $⋃_{i = 0}^{k} S_{i} = V (G)$ .
(b): $S_{i} \cap S_{j} = \emptyset$ for $0 \leq i < j \leq k$ .

7.

(k + 1)

-assignment of

V (G)

is a

(k + 1)

-partition

F = (F_{0}, \dots, F_{k})

V (G)

such that

w (F \otimes Q) \geq k

for every

Q \in Q (G) .

Remark 5.

For a fixed positive integer k, a

{k}

-maximum clique transversal function of a graph G can be regarded as a

(k + 1)

-assignment of

V (G)

, and vice versa. Then,

τ_{{k}} (G) = min {w (S) ∣ S

is a

(k + 1)

-assignment of

V (G)}

Definition 12.

Let k be a fixed positive integer and let G be a graph of bounded treewidth with a nice tree decomposition

(T, {B_{i} ∣ i \in T})

rooted at node r. For each node

i \in T

, let

X = (X_{0}, \dots, X_{k})

be a

(k + 1)

-partition of

B_{i}

and let

F_{i} (X)

be a

(k + 1)

-assignment

S = (S_{0}, \dots, S_{k})

V (G_{i})

of minimum weight satisfying all the following conditions.

(1): $S \otimes B_{i} = X$ .
(2): $w (S \otimes Q) \geq k$ for every $Q \in Q (G_{i}) \cap Q (G)$ .

F_{i} (X)

does not exist, let

F_{i} (X) = Φ

with

w (Φ) = \infty

Remark 6.

By Definition 12,

T = T_{r}

G = G_{r}

, and

τ_{{k}} (G) = min {w (F_{r} (X)) ∣ X

is a

(k + 1)

-partition of

B_{r}}

Lemma 10.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is a leaf node of T. For all

(k + 1)

-partitions X of

B_{i}

F_{i} (X)

G_{i}

can be computed in

O ({(k + 1)}^{t w (G) + 1} \cdot t w (G))

time.

Proof.

Since node i is a leaf node,

G_{i} = G [B_{i}]

and

Q (G_{i}) \cap Q (G) = Q (G [B_{i}])

. By the definition of tree decomposition,

| B_{i} | \leq t w (G) + 1

and

ω (G) = t w (G) + 1

. If

B_{i}

is not a maximum clique of G, then

F_{i} (X) = Φ

for every

(k + 1)

-partition X of

B_{i}

. It takes

O (t w {(G)}^{2})

time to check if

B_{i}

is a maximum clique. We therefore assume that

B_{i}

is a maximum clique of G. The number of

(k + 1)

-assignments of

B_{i}

{(k + 1)}^{t w (G) + 1}

. For each

(k + 1)

-assignment

F_{i} (X)

B_{i}

, we verify if

w (F_{i} (X)) \geq k

. The verification process can be done in

O (t w (G))

time. Following the discussion above, all

(k + 1)

-assignments

F_{i} (X)

G_{i}

can be computed in

O ({(k + 1)}^{t w (G) + 1} \cdot t w (G))

time. □

Lemma 11.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is a forget node of T. Let j be the child node of i and let

x \in B_{j}

such that

B_{i} = B_{j} \ {x}

. Let X be a

(k + 1)

-partition of

B_{i}

and

Y = {(X \oplus_{ℓ} {x}) ∣ 0 \leq ℓ \leq k}

. Let

Z \in Y

such that

w (F_{j} (Z)) = min {w (F_{j} (X^{'})) ∣ X^{'} \in Y}

. Then,

F_{i} (X) = F_{j} (Z)

Proof.

Since

B_{i} = B_{j} ∖ {x}

G_{i} = G_{j}

. The

(k + 1)

-assignment

F_{i} (X)

is also a

(k + 1)

-assignment of

V (G_{j})

. Let

X^{'} = F_{i} (X) \otimes B_{j}

. Then,

X^{'}

is a

(k + 1)

-partition of

B_{j}

. There exists exactly one integer

ℓ \in {0, 1, \dots, k}

such that

X^{'} = (X \otimes_{ℓ} {x})

. Let

Y = {(X \oplus_{ℓ} {x}) ∣ 0 \leq ℓ \leq k}

. Hence,

F_{i} (X) = F_{j} (Z)

, where

Z \in Y

and

w (F_{j} (Z)) = min {w (F_{j} (X^{'})) ∣ X^{'} \in Y}

. □

Lemma 12.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

. Suppose that node i is an introduce node of T. Let j be the child node of i and let x be the vertex such that

B_{i} = B_{j} \cup {x}

. Let

ℓ \in {0, 1, \dots, k}

and let

X = (X_{0}, \dots X_{k})

be a

(k + 1)

-partition of

B_{i}

such that

x \in X_{ℓ}

. Then,

F_{i} (X) = \{\begin{matrix} F_{j} (X ⊖_{ℓ} {x}) \oplus_{ℓ} {x} & i f e i t h e r B_{i} \notin Q (G), o r B_{i} \in Q (G) a n d w (X) \geq k, \\ Φ & o t h e r w i s e . \end{matrix}

Proof.

Let d be a proper descendant of the subtree

T_{j}

. Since

x \notin B_{j}

x \notin V (G_{j})

, by the third condition of Definition 5. Then,

x \notin B_{d}

. We consider the following two cases.

Case 1:

B_{i} \notin Q (G)

. By the arguments for the discussion of Case 1 in the proof of Lemma 6,

Q (G_{i}) \cap Q (G) = Q (G_{j}) \cap Q (G)

. For any

(k + 1)

-partition

X^{'}

B_{j}

w (F_{j} (X^{'}) \otimes Q)) \geq k

for every

Q \in Q (G_{i}) \cap Q (G)

Let

ℓ \in {0, 1, \dots, k}

and let X be a

(k + 1)

-partition of

B_{i}

such that

X = X^{'} \oplus_{ℓ} {x}

. Then,

F_{j} (X^{'}) \oplus_{ℓ} {x}

is a

(k + 1)

-assignment S of

V (G_{i})

such that

S \otimes B_{i} = X

. Therefore,

w (F_{i} (X)) \leq w (F_{j} (X^{'}) \oplus_{ℓ} {x})

Conversely, let

X = (X_{0}, X_{1}, \dots, X_{k})

be a

(k + 1)

-partition of

B_{i}

such that

x \in X_{ℓ}

. Then,

F_{i} (X) ⊖_{ℓ} {x}

is a

(k + 1)

-assignment

S^{'}

V (G_{j})

such that

S^{'} \otimes B_{j} = X ⊖_{ℓ} {x}

. Let

X^{'} = X ⊖_{ℓ} {x}

. Therefore,

w (F_{i} (X)) \geq w (F_{j} (X^{'}) \oplus_{ℓ} {x})

Following the discussion above, we know that

F_{i} (X) = F_{j} (X ⊖_{ℓ} {x}) \oplus_{ℓ} {x}

Case 2:

B_{i} \in Q (G)

. By the arguments for the discussion of Case 2 in the proof of Lemma 6,

Q (G_{i}) \cap Q (G) = (Q (G_{j}) \cap Q (G)) \cup {B_{i}}

. Since

B_{i} \in Q (G)

and

F_{i} (X) \otimes B_{i} = X

, we have

w (X) \geq k

. If

w (X) < k

, then

F_{i} (X)

does not exist. Following the arguments similar to those for proving Case 1, we know that

w (F_{i} (X)) = w (F_{j} (X^{'}) \oplus_{ℓ} {x})

. Therefore,

F_{i} (X) = F_{j} (X ⊖_{ℓ} {x}) \oplus_{ℓ} {x}

. □

Lemma 13.

Let G be a graph of bounded treewidth with a nice tree decomposition

(T, {B_{i} ∣ i \in T})

. Suppose that node i is a join node of T. Let j and ℓ be the child nodes of i. For each

(k + 1)

-partition

X = (X_{0}, X_{1}, \dots, X_{k})

B_{i}

F_{i} (X) = F_{j} (X) \oplus F_{ℓ} (X) .

Proof.

Since node i is a join node,

B_{i} = B_{j} = B_{ℓ}

. Then,

Q (G_{i}) = Q (G_{j}) \cup Q (G_{ℓ})

. Let

S = F_{j} (X) \oplus F_{ℓ} (X)

. Clearly,

S \otimes B_{i} = X

and

w (S \otimes Q) \geq k

for

Q \in Q (G_{i}) \cap Q (G)

. We have

w (F_{i} (X)) \leq w (S) = w (F_{j} (X) \oplus F_{ℓ} (X))

Let

S_{1} = F_{i} (X) \otimes V (G_{j})

and

S_{2} = F_{i} (X) \otimes V (G_{ℓ})

. Then,

S_{1}

and

S_{2}

are

(k + 1)

-assignments of

V (G_{j})

and

V (G_{j})

, respectively. Furthermore,

S_{1} \otimes B_{j} = S_{2} \otimes B_{ℓ} = X

. Therefore,

w (F_{j} (X) \oplus F_{ℓ} (X)) \leq w (S_{1} \oplus S_{2}) = w (F_{i} (X))

Following the discussion above,

w (F_{i} (X)) = w (F_{j} (X) \oplus F_{ℓ} (X))

and the lemma holds. □

Theorem 9.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

and

O (| V (G) |)

nodes. The

{k}

-maximum-clique transversal problem can be solved in

O ({(k + 1)}^{t w (G) + 1} \cdot t w (G) \cdot | V (G) |)

time.

Proof.

Assume that T is rooted at r. Then,

T = T_{r}

G = G_{r}

, and

τ_{\times k} (G) = min {w (F_{r} (X)) ∣ X

is a

(k + 1)

-partition of

B_{r}}

. Our algorithm works from the leaves in T up to the root, computing the solutions

F_{i} (X)

for each visited node i on the way through the dynamic programming technique. For all

(k + 1)

-partitions X of

B_{i}

, the solutions can be computed in

O ({(k + 1)}^{t w (G) + 1} \cdot t w (G))

time by Lemmas 10–13. Since T contains

O (| V (G) |)

nodes, the

{k}

-maximum-clique transversal problem can be solved in

O ({(k + 1)}^{t w (G) + 1} \cdot t w (G) \cdot | V (G) |)

time. □

4.3. The Signed and Minus Maximum-Clique Transversal Problems

The section deals with the signed and minus maximum-clique transversal problems on graphs of bounded treewidth.

Theorem 10.

Assume that

G = (V, E)

is a graph and

ω (G)

is fixed. Let

k = ⌊ ω (G) / 2 ⌋ + 1

. Then,

τ_{M}^{s} (G) = 2 τ_{\times k} (G) - n

Proof.

The theorem holds by Theorem 7 in Lee’s article [3]. □

Theorem 11.

Let

D = (T, {B_{i} ∣ i \in T})

be a nice tree decomposition of a graph G of width

t w (G)

and

O (| V (G) |)

nodes. The signed maximum-clique transversal problem can be solved in

O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time.

Proof.

It follows from Theorems 6 and 10. □

We introduce the 2-clique graph extension and positive maximum-clique transversal functions as follows.

Definition 13.

The 2-clique graph extension H of a graph G is defined as follows.

1.: $V (H) = {v_{1}, v_{2} ∣ v \in V (G)}$ .
2.: $E (H) = {v_{1} v_{2} ∣ v \in V (G)} \cup {u_{1} v_{1}, u_{1} v_{2}, u_{2} v_{1}, u_{2} v_{2} ∣ u v \in E (G)}$ .

Figure 3 shows an example of the 2-clique graph extension H of a graph G.

Definition 14.

Assume that G is a graph. A function

f : V (G) \to {0, 1, 2}

is a positive maximum-clique transversal function of G if

f (Q) \geq ω (G) + 1

for

Q \in Q (G)

. The positive maximum-clique transversal number of G, denoted by

τ_{M}^{+} (G)

, is the minimum weight of a positive maximum-clique transversal function of G. The positive maximum-clique transversal problem is to find a positive maximum-clique transversal function of G of minimum weight.

Lemma 14.

For any graph G,

τ_{M}^{+} (G) = τ_{M}^{-} (G) + | V (G) |

Proof.

Let f be a minus maximum-clique transversal function of G of minimum weight. We define a function h of G by

h (v) = f (v) + 1

for every

v \in V (G)

. Since

f (v) \in {- 1, 0, 1}

h (v) \in {0, 1, 2}

for

v \in V (G)

. Let Q be a maximum clique of G. Then

h (Q) = \sum_{v \in Q} (f (v) + 1) = f (Q) + | Q | \geq 1 + ω (G)

. The function h is a positive maximum-clique function of G. We have

τ_{M}^{+} (G) \leq τ_{M}^{-} (G) + | V (G) |

Conversely, let h be a positive maximum-clique transversal function of G of minimum weight. We define a function f of G by

f (v) = h (v) - 1

for every

v \in V (G)

. Since

h (v) \in {0, 1, 2}

f (v) \in {- 1, 0, 1}

for every

v \in V (G)

. Let Q be a maximum clique of G. Then

f (Q) = \sum_{v \in Q} (h (v) - 1) = h (Q) - | Q | \geq 1

. The function f is a minus maximum-clique function of G. We have

τ_{M}^{-} (G) \leq τ_{M}^{+} (G) - | V (G) |

. Following what we have discussed above, we know that

τ_{M}^{+} (G) = τ_{M}^{-} (G) + | V (G) |

. □

Lemma 15.

Assume that G is a graph with fixed clique number

ω (G)

. Let H be the 2-clique graph extension of G and

k = ω (G) + 1

. Then,

τ_{M}^{+} (G) = τ_{\times k} (H)

Proof.

Let

Q (G) = {C_{1}, \dots, C_{ℓ}}

and let

Q_{i} = {v_{1}, v_{2} ∣ v \in C_{i}}

for

1 \leq i \leq ℓ

. By the construction of H, it can be easily verified that

Q (H) = {Q_{1}, \dots, Q_{ℓ}}

Let f be a positive maximum-clique transversal function of G of minimum weight. We define a subset D of

V (H)

as follows.

For any vertex $v \in V (G)$ with $f (v) = 2$ , D includes both of the vertices $v_{1}$ and $v_{2}$ .
For any vertex $v \in V (G)$ with $f (v) = 1$ , D contains precisely one of the vertices $v_{1}$ and $v_{2}$ .
For any vertex $v \in V (G)$ with $f (v) = 0$ , D comprises none of the vertices $v_{1}$ and $v_{2}$ .

Let

i \in {1, \dots, ℓ}

. Then,

| D \cap Q_{i} | = \sum_{v \in C_{i}} | D \cap {v_{1}, v_{2}} | = \sum_{v \in C_{i}} f (v) = f (C_{i}) \geq ω (G) + 1 \geq k .

The set D is a k-fold maximum-clique transversal set of H. Hence,

τ_{\times k} (H) \leq τ_{M}^{+} (G)

Conversely, let S be a k-fold maximum-clique transversal set of H with

τ_{\times k} (H)

vertices. We define a function h of G as follows.

For any two vertices $v_{1}, v_{2} \in V (H)$ , $h (v) = 2$ if S includes both of them.
For any two vertices $v_{1}, v_{2} \in V (H)$ , $h (v) = 1$ if S contains precisely one of them.
For any two vertices $v_{1}, v_{2} \in V (H)$ , $h (v) = 0$ if S comprises none of them.

Let

i \in {1, \dots, ℓ}

. Then,

h (C_{i}) = \sum_{v \in C_{i}} h (v) = \sum_{v \in C_{i}} | S \cap {v_{1}, v_{2}} | = | S \cap Q_{i} | \geq k \geq ω (G) + 1 .

The function h is a positive maximum-clique transversal function of G. Hence,

τ_{M}^{+} (G) \leq τ_{\times k} (H)

. Following the discussion above, we have

τ_{M}^{+} (G) = τ_{\times k} (H)

. □

Theorem 12.

Assume that G is a graph with fixed clique number

ω (G)

. Let H be the 2-clique graph extension of G and

k = ω (G) + 1

. Then,

τ_{M}^{-} (G) = τ_{\times k} (H) - | V (G) |

Proof.

The theorem follows from Lemmas 14 and 15. □

Lemma 16.

Let G be a graph of bounded treewidth nd let H be a 2-clique graph extension of G. Given a nice tree decomposition

D = (T, B = {B_{i} ∣ i \in T})

of G of width

t w (G)

and

O (| V (G) |)

nodes, one can find a nice tree decomposition of H of width

2 (t w (G) + 1)

and with at most

4 | V (H) |

nodes in

O (| V (H) |)

time.

Proof.

Let

B_{i}^{'} = {v_{1}, v_{2} | v \in B_{i}}

for

B_{i} \in B

and

D^{'} = (T, B^{'} = {B_{i}^{'} ∣ i \in T})

. We show as follows that

D^{'}

is a tree decomposition of H.

(1): Every vertex $v \in V (G)$ appears in at least one bag of B. Suppose that $v \in B_{i}$ . Since $V (H) = {v_{1}, v_{2} ∣ v \in V (G)}$ , $v_{1}, v_{2} \in B_{i}^{'}$ . Therefore, every vertex of H appears in at least one bag $B_{i}^{'} \in B^{'}$ .
(2): For each edge $e = u v \in E (G)$ , there is at least one bag of B containing the vertices u and v. Suppose that $u, v \in B_{i}$ . Since $E (H) = {v_{1} v_{2} ∣ v \in V (G)} \cup {u_{1} v_{1}, u_{1} v_{2}, u_{2} v_{1}, u_{2} v_{2} ∣ u v \in E (G)}$ , $u_{1}$ , $u_{2}$ , $v_{1}$ , and $v_{2}$ , are in the bag $B_{i}^{'}$ . Therefore, there is at least one bag of $B^{'}$ containing both x and y for all edges $x y \in E (H)$ .
(3): Let $v \in V (G)$ . Then, $v_{1}, v_{2} \in V (H)$ . Clearly, $v_{1}, v_{2} \in B_{i}^{'}$ if and only if $v \in B_{i}$ . By Lemma 1, if v appears in two bag $B_{p}, B_{q} \in B$ , then it appears in every bag $B_{j}$ for the node j on the tree path from node p to node q in T. Since $V (H) = {v_{1}, v_{2} ∣ v \in V (G)}$ , $v_{1}$ and $v_{2}$ are both in $B_{p}^{'}$ and $B_{q}^{'}$ and they appear in every bag $B_{j}^{'}$ for the node j on the tree path from node p to node q in T.

Following the discussion above,

D^{'} = (T, B^{'})

is a tree decomposition of H of width

2 (t w (G) + 1)

and with

O (| V (G) |)

nodes. By Lemma 2, we can obtain a nice tree decomposition of H of width

2 (t w (G) + 1)

with at most

4 | V (H) |

nodes in

O (| V (H))

time. □

Theorem 13.

Let G be a graph of bounded treewidth. Given a nice tree decomposition

D = (T, B = {B_{i} ∣ i \in T})

of G of width

t w (G)

and

O (| V (G) |)

nodes, the minus maximum-clique transversal problem can be solved in

O (4^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time.

Proof.

Let H be the 2-clique graph extension of G. By Lemma 16, we can obtain a nice tree decomposition of H of width

2 (t w (G) + 1) - 1

with at most

4 | V (H) |

nodes in

O (| V (H) |)

time. Since G is a graph of bounded treewidth, H is a graph of bounded treewidth

2 (t w (G) + 1) - 1

. Note that

| V (H) | = 2 \cdot | V (G) |

. By Theorems 6 and 7, the minus maximum-clique transversal function problem can be solved in

O (4^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time. □

Remark 7.

The complexity of the minus maximum-clique transversal problem for graphs of bounded treewidth can be improved to

O (3^{t w (G)} \cdot t w (G) \cdot | V (G) |)

by our dynamic programming technique used for the

{k}

-maximum-clique transversal problem. We leave it to interested readers.

5. Conclusions

In this paper, we have shown that the k-fold maximum-clique transversal problem can be solved in

O (2^{t w (G)} \cdot t w (G) \cdot | V (G) |)

time for any graph G with bounded treewidth

t w (G)

. The maximum-clique transversal problem is a particular case of the k-fold maximum-clique transversal problem and the

{k}

-maximum-clique transversal problem with

k = 1

. Therefore, the problem can be solved in the same running time. Lokshtanov et al. [18] obtained a number of lower bounds on the running time of algorithm solving problems on graphs of bounded treewidth under the strong exponential time hypothesis (SETH) of Impagliazzo and Paturi [19]. Based on SETH, we conjecture that the maximum-clique transversal problem cannot be solved in

{(2 - ϵ)}^{t w (G)} {| V (G) |}^{O (1)}

time for any

ϵ > 0

. Although SETH is still somewhat controversial and not entirely accepted by the computational complexity community, the lower bound still delivers valuable messages. If the lower bound can be obtained under SETH, then the

{k}

-maximum-clique transversal problem cannot be solved in in

{(k + 1 - ϵ)}^{t w (G)} {| V (G) |}^{O (1)}

time for any

ϵ > 0

. Our algorithms on graphs of bounded treewidth are probably optimal. Finally, we suggest the following open questions for future work:

(1): Table 1 and Table 2 show that the respective parameterized complexities of the clique transversal, k-fold maximum-clique transversal, and ${k}$ -maximum-clique transversal problems remain unknown for planar graphs. Can we find fixed-parameter tractable algorithms to solve them for planar graphs if the considered problem is parameterized by the solution size or weight? Or is it possible to find improved algorithms for planar graphs of bounded treewidth?
(2): In Table 2, all the considered problems parameterized by treewidth are fixed-parameter tractable. Can we prove that all the considered problems remain fixed-parameter tractable if given other parameters?
(3): This paper considers only maximum cliques for simple graphs. In reality, dicliques also appear in more general directed graphs [20]. It is interesting to consider the problems for directed ones.

Funding

This research is supported by a Taiwanese grant under Grant No. NSC-97-2218-E-130-002-MY2.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

We are grateful to the anonymous referees for their valuable comments and suggestions to improve the presentation of this paper.

Conflicts of Interest

The author declares no conflict of interest.

References

Chang, M.S.; Kloks, T.; Lee, C.M. Maximum clique transversals. In Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, Boltenhagen, Germany, 14–16 June 2001; Lecture Notes in Computer Science: Berlin, Germany, 2001; pp. 32–43. [Google Scholar]
Lee, C.-M.; Chang, M.-S. Signed and minus clique-transversal function on graphs. Inform. Process. Lett. 2009, 109, 414–417. [Google Scholar] [CrossRef]
Lee, C.-M. Variations of maximum-clique transversal sets on graphs. Ann. Oper. Res. 2010, 181, 21–66. [Google Scholar] [CrossRef]
Lee, C.-M. Weighted maximum-clique transversal sets of graphs. ISRN Discrete Math. 2011, 2011, 32–43. [Google Scholar] [CrossRef] [Green Version]
Lee, C.-M. Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs. Algorithms 2021, 14, 22. [Google Scholar] [CrossRef]
Liu, K.; Lu, M. Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs. J. Combin. Optim. 2021, 41, 923–933. [Google Scholar] [CrossRef]
Wang, H.; Kang, L.; Shan, E. Signed clique-transversal functions in graphs. Int. J. Comput. Math. 2010, 87, 2398–2407. [Google Scholar] [CrossRef]
Wang, H.; Shan, E. The signed maximum-clique transversal number of regular graphs. Int. J. Comput. Math. 2012, 89, 741–751. [Google Scholar] [CrossRef]
Xu, G.; Shan, E.; Kang, L.; Chang, T.C.E. The algorithmic complexity of the minus clique-transversal problem. Appl. Math. Comput. 2007, 189, 1410–1418. [Google Scholar] [CrossRef]
Downey, R.G.; Fellows, M.R. Parameterized Complexity; Monographs in Computer Science; Springer: New York, NY, USA, 1999. [Google Scholar]
Alber, J.; Bodlaender, H.; Fernau, H.; Kloks, T.; Niedermeier, R. Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs. Algorithmica 2002, 33, 461–493. [Google Scholar] [CrossRef]
Brandstädt, A.; Le, V.B.; Spinrad, J.P. Graph Classes—A Survey; SIAM Monographs on Discrete Mathematics and Applications; SIAM: Philadelphia, PA, USA, 1999. [Google Scholar]
Rose, D.J. Triangulated graphs and the elimination process. J. Math. Anal. Appl. 1970, 32, 597–609. [Google Scholar] [CrossRef] [Green Version]
Kloks, T. Treewidth—Computations and Approximations; Lecture Notes in Computer Science: Berlin, Germany, 1993; p. 842. [Google Scholar]
Arnbor, S.; Proskurowski, A. Characterization and recognition of partial 3-trees. SIAM J. Alg. Discete Meth. 1986, 7, 305–314. [Google Scholar] [CrossRef]
Bodlaender, H.; Möhring, R.H. The pathwidth and treewidth of cographs. SIAM J. Discrete Math. 1993, 6, 181–188. [Google Scholar] [CrossRef] [Green Version]
Alhevaz, A.; Darkooti, M.; Rahbani, H.; Shang, Y. Strong Equality of Perfect Roman and Weak Roman Domination in Trees. Mathematics 2019, 7, 997. [Google Scholar] [CrossRef] [Green Version]
Lokshtanov, D.; Marx, D.; Saurabh, S. Known Algorithm on Graphs of Bounded Treewidth Are Probably Optimal. ACM Trans. Algorithms 2018, 14, 30. [Google Scholar] [CrossRef] [Green Version]
Impagliazzo, R.; Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sci. 2001, 62, 275–291. [Google Scholar] [CrossRef] [Green Version]
Shang, Y. Large dicliques in a directed inhomogeneous random graph. Int. J. Comput. Math. 2013, 90, 445–456. [Google Scholar] [CrossRef]

Figure 1. (a) A graph G. (b) A nice tree decomposition of G.

Figure 2. (a) A graph G with two maximal cliques. (b) A complete graph H. (c) The strong product of G and H.

Figure 3. (a) A graph G with two maximal cliques. (b) The 2-clique graph extension H of G.

Table 1. Previous results and our fixed parameter intractable results.

Parameter: The Solution Size or Weight
Graphs	CTP	$k$ -FMCTP	${k}$ -MCTP	SMCTP	MMCTP
Chordal	$W [2]$ -c $^{*}$	$W [2]$ -c [1]	$W [2]$ -c [1]	para-NP-c $^{*}$	−
		( $k = 1$ )	( $k = 1$ )
Doubly Chordal	−	−	−	para-NP-c $^{*}$	−
Split	$W [2]$ -c $^{*}$	−	−	−	−
Planar	−	−	−	para-NP-c $^{*}$	para-NP-c $^{*}$

Table 2. Previous results and our fixed parameter tractable results.

Problem	Bounded Treewdith Graph	Planar Graph
Problem	Parameter: Treewidth t	Parameter: The Solution Size ℓ
CTP	$O (4^{t} \cdot t \cdot n)$ [6]	*−
MCTP	$O {(2^{t} \cdot t \cdot n)}^{*}$	$min {O (ω^{ℓ} \cdot ℓ^{2} + n), O (c^{\sqrt{ℓ}} \cdot ℓ^{2} + n)}$ [1]
k-FMCTP	$O {(2^{t} \cdot t \cdot n)}^{*}$	−
${k}$ -MCTP	$O {({(k + 1)}^{t + 1} \cdot t \cdot n)}^{*}$	−
SMCTP	$O {(2^{t} \cdot t \cdot n)}^{*}$	−
MMCTP	$O {(3^{t} \cdot t \cdot n)}^{*}$	−

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Lee, C.-M. Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs. Symmetry 2022, 14, 676. https://doi.org/10.3390/sym14040676

AMA Style

Lee C-M. Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs. Symmetry. 2022; 14(4):676. https://doi.org/10.3390/sym14040676

Chicago/Turabian Style

Lee, Chuan-Min. 2022. "Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs" Symmetry 14, no. 4: 676. https://doi.org/10.3390/sym14040676

APA Style

Lee, C. -M. (2022). Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs. Symmetry, 14(4), 676. https://doi.org/10.3390/sym14040676

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs

Abstract

1. Introduction

2. Definitions and Notations

3. The Fixed-Parameter Intractable Results

4. Fixed-Parameter Tractable Results for Graphs of Bounded Treewidth

4.1. The k-Fold Maximum-Clique Transversal Problem

4.2. The ${k}$ -Maximum-Clique Transversal Problem

4.2.1. Problem Solving by Reduction

4.2.2. Problem Solving by Dynamic Programming

4.3. The Signed and Minus Maximum-Clique Transversal Problems

5. Conclusions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs

Abstract

1. Introduction

2. Definitions and Notations

3. The Fixed-Parameter Intractable Results

4. Fixed-Parameter Tractable Results for Graphs of Bounded Treewidth

4.1. The k-Fold Maximum-Clique Transversal Problem

4.2. The { k } -Maximum-Clique Transversal Problem

4.2.1. Problem Solving by Reduction

4.2.2. Problem Solving by Dynamic Programming

4.3. The Signed and Minus Maximum-Clique Transversal Problems

5. Conclusions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

4.2. The ${k}$ -Maximum-Clique Transversal Problem