1 Introduction

1.1 Complexity of toughness

All graphs considered in this paper are finite, simple, and undirected. Let C(G) denote the set of components of G and let \(c(G)=|C(G)|\), i.e. the number of components. If \(S\subseteq V(G)\), then \(G-S\) denotes the graph obtained by deleting all vertices of S from G. For a connected graph G, a vertex set \(S\subseteq V(G)\) is called a cutset if \( c(G-S)>1\).

The notion of toughness was introduced by Chvátal in [12].

Definition 1

Let t be a real number. A graph G is called t-tough if \(|S| \ge t \cdot c(G-S)\) for any \(S \subseteq V(G)\) with \(c(G-S)>1\). The toughness of G, denoted by \(\tau (G)\), is the largest t for which G is t-tough, taking \(\tau (K_n) = \infty \) for all \(n \ge 1\).

Note that a graph is disconnected if and only if its toughness is 0.

The relation of toughness to Hamiltonian cycles, connectivity, and other measures of graph robustness are well researched topics. There are quite a few results on the computational aspects of toughness.

Let t be an arbitrary positive rational number and consider the following problem.

\(\varvec{t}\)-Tough

Instance: a graph G.

Question: is it true that \(\tau (G) \ge t\)?

It is easy to see that for any positive rational number t the problem t-Tough is in coNP: a witness is a vertex set S whose removal disconnects the graph and leaves more than |S|/t components. Bauer et al. proved that this problem is coNP-complete [2]. The problem 1-Tough remains coNP-complete for at least 3-regular graphs [5].

Theorem 1

([2]) For any positive rational number t, the problem t-Tough is coNP-complete.

Theorem 2

([5]) For any fixed integer \(r \ge 3\), the problem 1-Tough is coNP-complete for r-regular graphs.

Although the toughness of any bipartite graph (except for the graphs \(K_1\) and \(K_2\)) is at most one, the problem 1-Tough does not become easier for bipartite graphs, and the same is true for smaller t values.

Theorem 3

([19]) The problem 1-Tough is coNP-complete for the class of bipartite graphs.

Theorem 4

([17]) For any positive rational number \(t \le 1\) the problem t-Tough remains coNP-complete for bipartite graphs.

In [17], the authors prove similar results for different sub-classes of bipartite graphs. A good survey of further results is [10].

It is widely believed that these complexity results imply that there is no polynomial algorithm that computes the toughness of a given graph even for these special graph classes. On the other hand, for some other graph classes, we do have such algorithms. The first example is the class of claw-free graphs. Since the toughness of a claw-free graph is half of its connectivity [20], and the connectivity of any graph can be computed in polynomial time, so is the toughness of claw-free graphs. Another class of graphs for which this is the case is the class of split graphs. In [19], it was shown that the class of 1-tough graphs can be recognized in polynomial time, and in [23] the same was proved for t-tough split graphs with \(t\ge 0\). This was further extended to a larger class, namely to the class of \(2K_2\)-free graphs [11]. These are graphs that do not contain an induced copy of \(2K_2\), the graph on four vertices consisting of two vertex-disjoint edges. It is easy to see that every split graph is a \(2K_2\)-free graph.

Theorem 5

([11]) The toughness of a \(2K_2\)-free graph can be determined in polynomial time.

For interval graphs, [18] contains a polynomial algorithm to compute the toughness.

For some special values of t there are also polynomial algorithms to compute the toughness of some regular graphs. For instance, the characterization of 3-regular 3/2-tough graphs in [15] implies that these graphs can be recognized in polynomial time. Some further results are the following.

Theorem 6

([17]) For any positive rational number \(t < 2/3\) there is a polynomial-time algorithm to recognize t-tough 3-regular graphs.

Theorem 7

([17]) There is a polynomial-time algorithm to recognize 1/2-tough 4-regular graphs.

1.2 Treewidth

The notion of treewidth is proposed in [21, 22], it is a famous parameter in complexity problems. Here we follow the notations of [7]. We use \(2^V\) to denote the power-set of a set V. Given a graph \(G=(V, E)\), a tree decomposition of G is a pair \(\mathcal {T}=(\mathcal {X}, T)\) where \(\mathcal {X}=\left\{ X_b \mid b \in B\right\} \subseteq 2^V\) and \(T=( B, F)\) is a tree satisfying:

  1. 1.

    \(\cup _{b \in B} X_b=V\),

  2. 2.

    for all edges \(\{u, v\} \in E\), there exists \(b \in B\) such that \(\{u, v\} \subseteq X_b\),

  3. 3.

    for all \(i, j, k \in B\), if j is on the path from i to k in T, then \(X_i \cap X_k \subseteq X_j\).

The elements of set \(\mathcal {X}\) which correspond to the nodes of tree T are called bags. Note that the last condition can be substituted by the following equivalent condition:

  1. 3.

    for each \(v \in V\), the set of nodes \(\left\{ b \in B \mid v \in X_b\right\} \) forms a subtree of T.

The width of the tree decomposition \(\mathcal {T}=(\mathcal {X}, T)\) is \(\max _{b\in V(T)} |X_b|-1\). The treewidth of a graph G is the minimum width of a tree decomposition of G.

We use the term vertex for the elements of V, nodes for the elements of B, and bags for the elements of \(\mathcal {X}\). We say the set \(X_b\) is the corresponding bag to node \(b \in B\) in tree T.

Computing the treewidth of an arbitrary graph is an NP-hard problem [1]. However, if the treewidth is bounded, it can be computed in polynomial time [8].

A tree decomposition \(\mathcal {T}\) of a graph G can be made rooted by designating a bag as the root bag. A rooted tree decomposition is called nice [9] whenever each bag \(X_i\in \mathcal {X}\) is one of the following types:

  • leaf bag: the node i has no child in T,

  • forget bag: the node i has exactly one child j where \(X_i \subseteq X_j\) and \(\left| X_i\right| =\left| X_j\right| -1\),

  • introduce bag: the node i has exactly one child j such that \(X_j \subseteq X_i\) and \(\left| X_i\right| =\left| X_j\right| +1\),

  • join bag: the node i has exactly two children j and \(j'\) where \(X_i=X_j=X_{j'}\).

The nodes of T that correspond to the above bags are called leaf, forget, introduce and join nodes, respectively.

A nice tree decomposition is called very nice if all leaf bags have size 1.

Given a tree decomposition \(\mathcal {T}\) of G of width \(\textrm{tw}(G)\) with \({\mathcal {O}}(n)\) bags, then a very nice tree decomposition of width \(\textrm{tw}(G)\) can be obtained with at most \(\mathcal {O}(4 n)\) bags in \(\mathcal {O}(n)\) time [9]. Thus we can assume that we are already given a very nice tree decomposition of G.

There are many decision problems on graphs that are NP-complete in general but can be solved in polynomial time for graphs with bounded treewidth using dynamic programming. See [14] for further details.

In Sect. 2 we describe the algorithm to compute the toughness for a given graph G assuming that very nice tree decomposition of G is also given. In Sect. 3 first we prove some useful lemmas, then we state the main result and prove it.

2 The algorithm

First notice that for a non-complete, connected graph G on n vertices the toughness \(\tau (G)\) is a rational number \(\frac{p}{q}\) with \(1\le p,q \le n\). So if we have an algorithm that computes the maximum number of components after the removal of s vertices for any integer \(0\le s < n\), then the toughness can be easily determined by finding the minimum ratio.

We use a dynamic programming approach to solve this modified problem, similar to many of the known algorithms in the literature.

Take the given very nice rooted tree decomposition. Let \(V_ b\) denote the set of all vertices of G appearing in bags that are descendants of b, and \({G_ b}:=G[V_ b]\).

Compute the following function in the rooted tree T for each vertex \( b\in B=V(T)\) in a bottom up order (i.e. first for the leafs, then for their parents, etc.):

\({\textsc {Mnc}}( b,s,Q,\mathcal {P}):=\) the maximum number of components of \(G_ b-S\) where the maximum is taken for all sets \(S\subseteq V_b\) having

  • \(|S|=s\),

  • \(S\cap X_b=Q\), and

  • \(\mathcal {P}\) is the partition of \(X_b-Q=X_b-S\) where two vertices belong to the same set iff they belong to the same component of the graph \(G_b-S\).

If there is no S that satisfies the above conditions, then \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) is not defined (so there is no need to compute it). However, it can be considered to be 0. For simplicity, we will refer to these sets S as cutting-sets, but note that such a set is not necessarily a cutset, \(c(G-S)\) can be 1.

For every \(b\in B\) compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) for each possible value of \(0\le s<n\), set \(Q\subseteq X_b\) and partition \(\mathcal {P}\) using the previously computed information for the child/children of b. We say that the information stored in a node is the collection of all these values.

Finally, for the root r of the tree, compute

$$\begin{aligned}\tau (G)=\min \left\{ \left. \frac{s}{{\textsc {Mnc}}(r,s,Q,\mathcal {P})}\ \right| \ 0\le s<n,\ {\textsc {Mnc}}(r,s,Q,\mathcal {P})\ge 2\right\} .\end{aligned}$$

3 Lemmas, results, and proofs

First, we introduce some notations about partitions that we use in the proof. A partition \(\mathcal {P}_A=\{A_1,\ldots ,A_p\}\) of a set A is a set of nonempty subsets \(A_i\subseteq A\) that are pairwise disjoint and \(\cup _{i=1}^p A_i=A\). The sets \(A_i\) are called blocks. For convenience, \(\mathcal {P}_A\cup \{\emptyset \}\) is considered to be the same as \(\mathcal {P}_A\), although technically, it is not a partition. If \(x\notin A\) then we say that the partition \(\mathcal {P}_A\) does not cover x. If the context is clear, then the subscript can be omitted. The partition \(\{A\}\) is called a trivial partition. If \(a\in A\) and \(\mathcal {P}_A\), then we denote by \(\mathcal {P}_A-a\) the partition \(\{A_1-\{a\}, \ldots ,A_i-\{a\}, \ldots , A_p-\{a\}\}\). Clearly, \(a\in A_i\) holds for exactly one i, so only that set is changed. When \(A'\subset A\) then the partition \(\mathcal {P}_A\) induces the partition \(\mathcal {P}_{A'}=\{A_1\cap A',\ldots ,A_p\cap A'\}\) on \(A'\). (If some \(A_i\cap A'=\emptyset \), then our convention removes this set from the partition.) We say that a partition \(\mathcal {Q}_A=\{B_1,\ldots , B_q\}\) is a refinement of \(\mathcal {P}\), denoted by \(\mathcal {P}\sqsubseteq \mathcal {Q}_A\), if each \(B_i\) is a subset of some \(A_j\). Also, \(\mathcal {Q}\) is a single-refinement of \(\mathcal {P}\) if \(B_i=A_i\) holds for \(i=1,\ldots ,k-1,k+1,\ldots ,p\) and \(\{B_{i+1}, \ldots ,B_q\}\) is a partition of \(A_k\). The join of two partitions \(\mathcal {P}\) and \(\mathcal {Q}\), denoted by \(\mathcal {P}\sqcup \mathcal {Q}\), is the most refined partition \(\mathcal {R}\) that satisfies \(\mathcal {R}\sqsubseteq \mathcal {P}\) and \(\mathcal {R}\sqsubseteq \mathcal {Q}\). If we imagine two arbitrary graphs \(G_P\), \(G_Q\) on the same vertex set U, where the family of connected components of \(G_P\) is \(\mathcal {P}\) and the family of connected components of \(G_Q\) is \(\mathcal {Q}\), then \(\mathcal {P}\sqcup \mathcal {Q}\) corresponds to the set of connected components in the union of \(G_P\) and \(G_Q\) [14].

Lemma 1

The total size of information for one node of \(\mathcal {T}\) is

$$\begin{aligned} {\mathcal {O}}\left( |V(G)|\cdot \textrm{tw}(G)^{\textrm{tw}(G)}\right) . \end{aligned}$$

Proof

For each bag we keep track of the maximum number of components in \(G_b-S\) for all possible combination of \(s,Q,\mathcal {P}\). Since \(s=|S|\), we have \(0\le s\le |V(G)|-1\), so there are |V(G)| choices for s.

\(\mathcal {P}\) is a partition of \(X_b-Q\), so the pair \(Q,\mathcal {P}\) can be considered as a partition of \(X_b\) where one of the blocks (i.e. Q) is marked. We know that \(|X_b|\le \textrm{tw}(G)+1\). It is known [6] that the number of different partitions of an n element set is bounded by \(\left( {0.792n}/{\ln (n+1)}\right) ^{n}\). Any of the blocks can be marked, so the number of possibilities is bounded by

$$\begin{aligned} n\left( \frac{0.792n}{\ln (n+1)}\right) ^n={\mathcal {O}}{\left( (n-1)^{n-1}\right) }={\mathcal {O}}\left( \textrm{tw}(G)^{\textrm{tw}(G)}\right) . \end{aligned}$$

\(\square \)

Lemma 2

If b is a leaf node in the very nice tree decomposition, then \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) can be computed in \({\mathcal {O}}(1)\) time.

Proof

Since b is a leaf in a very nice tree decomposition, we have \(|X_b|=1\). It is clear that if \(s=0\), then \(S=\emptyset \). This implies that \(Q=\emptyset \) and \(\mathcal {P}\) is the partition \(\{X_b\}\). Therefore \({\textsc {Mnc}}(b,0,\emptyset ,\{X_b\})=1\).

On the other hand, if \(s=1\), then the only values that satisfy the conditions are \(S=X_b\), \(Q=X_b\), and \(\mathcal {P}=\emptyset \). Therefore \({\textsc {Mnc}}(b,1,X_b, \emptyset )=0\).

Since there are only two values to compute, it is clear, that this can be done in \({\mathcal {O}}(1)\) time. \(\square \)

Lemma 3

If b is a forget node in the very nice tree decomposition then \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) can be computed in \({\mathcal {O}}(\textrm{tw}(G))\) time.

Proof

Let \(b'\) denote the only child of b in T and let \(f\in V\) be the vertex we “forget”, i.e. \(X_{b'}=X_b\cup \{f\}\) (and \(f\notin X_b\)). To compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) we need to consider all cutting-sets \(S\subset V_b\) that match the parameters. Each cutting-set either contains the vertex f or it does not. Let us compute the maximum number of components in \(G_b-S\) separately for these two types of cutting-sets.

Case 1: \(f\in S\).:

We claim that in this case the maximum number of components is \({\textsc {Mnc}}(b',s,Q\cup \{f\}, \mathcal {P})\). It is enough to show that the maximum is taken for the same set of cutting-sets in both functions. First, note that \(f\in X_{b'}\cap S=Q\cup \{f\}\) holds, thus \(\mathcal {P}\) does not cover f. In \({\textsc {Mnc}}(b',s,Q\cup \{f\}, \mathcal {P})\) we only consider those cutting-sets that contain f (and Q). This implies that \(C(G_b-S)=C(G_{b'}-S)\), since \(G_b=G_{b'}\). Clearly, they also induce the same partition on \(X_b-S\) and \(X_{b'}-S\), so the parameter \(\mathcal {P}\) is the same in both functions.

Case 2: \(f\notin S\).:

In this case, \(C(G_b-S)\) induces the partition \(\mathcal {P}\) on \(X_b-S\). \(C(G_{b'}-S)\) also induces some partition \(\mathcal {P'}\) on \(X_{b'}-S=(X_b-S)\cup \{f\}\). Since \(C(G_b-S)=C(G_{b'}-S)\), it is clear, that the two partitions should essentially be the same, i.e. \(\mathcal {P'}-f=\mathcal {P}\) must hold. Therefore, the maximum number of components in this case is

$$\begin{aligned} \max \{{\textsc {Mnc}}(b',s,Q,\mathcal {P'})\mid \mathcal {P'}-f=\mathcal {P}\}, \end{aligned}$$

since we consider the same set of cutting-sets.

Finally, to compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\), we take the maximum of the values obtained in the above cases.

The computation time in Case 1 is clearly constant. In Case 2, fortunately it is easy to obtain all the partitions \(\mathcal {P'}\) that satisfy the condition by simply adding f to one of the sets in partition \(\mathcal {P}\). Since size of \(\mathcal {P}\) is bounded by \(\textrm{tw}(G)\), the time bound is \({\mathcal {O}}(\textrm{tw}(G))\). \(\square \)

Lemma 4

If b is an introduce node in the very nice tree decomposition, then \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) can be computed in \({\mathcal {O}}(\textrm{tw}(G)^{\textrm{tw}(G)})\) time.

Proof

Let \(b'\) denote the only child of b in T and let \(i\in V\) be the vertex we “introduce”, i.e. \(X_{b'}=X_b- \{i\}\) (and \(i\in X_b\)). Like in the proof of Lemma 3, to compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) we need to consider all cutting-sets \(S\subset V_b\) that match the parameters. Let us compute the maximum number of components in \(G_b-S\) separately for cutting-sets containing i and the ones not containing it. Note that \(G_{b'}=G_b-i\) and \(V_{b'}=V_b-\{i\}\).

Case 1: \(i\in S\).:

We claim that in this case the maximum number of components is \({\textsc {Mnc}}(b',s-1,Q- \{i\}, \mathcal {P})\). It is enough to show that a cutting-set S of \(G_b\) satisfying \(i\in S\) matches the parameters in \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) if and only if \(S'=S-\{i\}\) matches the parameters of \({\textsc {Mnc}}(b',s-1,Q- \{i\}, \mathcal {P})\), and \(c(G_b-S)=c(G_{b'}-S')\) holds. First, \(|S'\cap V_{b'}|=s-1\) holds because \(|S\cap V_{b}|=s\) and \(i\notin V_{b'}\). Also, \(S'\cap X_{b'}=Q-\{i\}\) is true for similar reasons. Finally, note that \(C(G_b-S)=C(G_{b'}-S')\), thus \(c(G_b-S)=c(G_{b'}-S')\). This also implies that these components induce the same partition \(\mathcal {P}\) on \(X_b-S\) and \(X_{b'}-S'\) simply because \(X_b-S=X_{b'}-S'\).

Case 2: \(i\notin S\).:

In this case S is also a cutting-set of \(G_{b'}\) with \(|S|=s\) and \(S\cap X_{b'}=Q\). Since \(i\notin S\), the vertex i belongs to one of the components of \(G_b-S\). It is possible that i is a cut-vertex in this component. Since we obtain the components of \(G_{b'}-S\) by deleting the vertex i from its component, this component may fall to several components, but the other components will not change. Let \(\mathcal {C}_{V_b-S}=\{C_1,\ldots ,C_p\}\) be the partition that the components of \(G_b-S\) induces, we may assume that \(i\in C_1\). Now let \(\mathcal {D}_{V_{b'}-S}=\{D_1,\ldots ,D_q,C_2,\ldots ,C_p\}\) be the partition that the components of \(G_{b'}-S\) induced. This implies that i must have a neighbor in each \(D_j\) block, but there may be more than one neighbor in the same block. Note that all such neighbors of i must belong to \(X_{b'}\) because of the structure of the tree decomposition. We know that \(\mathcal {C}\) induces \(\mathcal {P}=\{A_1,\ldots ,A_{p'}\}\) on \(X_b-S\), let \(\mathcal {P'}=\{B_1,\ldots ,B_{q'}, A_2,\ldots ,A_{p'}\}\) denote the partition \(\mathcal {D}\) induced on \(X_{b'}-S\). Again, this implies that i must have a neighbor in each \(B_j\) block, but there may be more than one neighbor in the same block. Of course, we may obtain a different refinement of \(\mathcal {P}\) if the cutting-set is different. Which partitions can we obtain? We say that \(\mathcal {P}'\) is an i-refinement of \(\mathcal {P}\) if it is obtained from \(\mathcal {P}\) by first deleting the vertex i from it, then taking a refinement of the block that contained i, so that each sub-block contains at least one neighbor of i. Therefore, the maximum number of components in this case is

$$\begin{aligned} \max \{{\textsc {Mnc}}(b',s,Q,\mathcal {P'})-|\mathcal {P'}|+|\mathcal {P}|\mid \mathcal {P'} \text { is an }i\text {-refinement of }\mathcal {P}\}, \end{aligned}$$

since the above argument shows that we consider the same set of cutting-sets. It is important to mention that there may be some \(\mathcal {P'}\) partitions that are i-refinements of \(\mathcal {P}\), but there is no cutting-set that realizes it. For example, if v and w are two neighbors of i belonging to different \(B_j\) blocks, but v and w are adjacent in the graph, no S can separate them. However, in these cases, \({\textsc {Mnc}}(b',s,Q,\mathcal {P'})\) is not defined, so we consider it to be 0, and it does not affect the maximum.

Finally, to compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\), we take the maximum of the values obtained in the above cases.

The computation time in Case 1 is constant. In Case 2, we must compute all i-refinements of \(\mathcal {P}\). The worst case is that \(\mathcal {P}\) has size one, and i is connected to all of its vertices. In this case, we need to take all partitions of \(X_b\). Its size is bounded by \(\textrm{tw}(G)+1\), so the number of partitions is bounded \({\mathcal {O}}(\textrm{tw}(G)^{\textrm{tw}(G)})\) (see the proof of Lemma 1); hence the total time bound in this case is \({\mathcal {O}}(\textrm{tw}(G)^{\textrm{tw}(G)})\). \(\square \)

Lemma 5

If b is a join node in the very nice tree decomposition, then for any fixed s value \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) can be computed for all possible pairs of Q and \(\mathcal {P}\) in \({\mathcal {O}}(|V(G)|\cdot \textrm{tw}(G)^{2\textrm{tw}(G)})\) time.

Proof

Let \(b'\) and \(b''\) denote the two children of b in T. Since b is a join node, we have \(X_{b}=X_{b'}=X_{b''}\), and \(V_{b'}\cap V_{b''}=X_b\). Unlike in the previous lemmas, to compute \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) we do not consider all cutting-sets \(S\subset V_b\) that match the parameters. Let \(S\cap V_{b'}=S'\) and \(S\cap V_{b''}=S''\). By the properties of the tree decomposition, \(S'\cap S''=S\cap X_b=Q\) holds. We show that it is enough to consider those cutting-sets where \(S'\) and \(S''\) are optimal. \(\square \)

Claim

Let Q and \(\mathcal {P}\) be fixed, and let S be a cutting-set such that \(c(G_b-S)\) is maximal among the cutting-sets matching the parameters (i.e., \(S\cap V_b=Q\) and \(C(G_b-S)\) induces the partition \(\mathcal {P}\) on \(X_b\)). This implies that \(c(G_{b'}-S')\) is maximal among the cutting-sets matching the same parameters. Similar claim holds for \(S''\).

Proof

Suppose that \(c(G_{b'}-S')\) is not maximal, let \(R'\subseteq V_{b'} \) be a cutting-set that matches the same parameters, and \(c(G_{b'}-R')> c(G_{b'}-S')\). Now define \(R=S''\cup R'\), i.e. replace \(S'\) with \(R'\) (or \(S'-Q\) with \(R'-Q\)) to obtain a new cutting-set of \(G_b\). Note that R matches the same parameters (Q and \(\mathcal {P}\)).

There are three types of components in \(G_b-S\): The ones that are contained entirely in \(V_{b'}\); the ones that are contained in \(V_{b''}\); and the ones that intersect both \(V_{b'}\) and \(V_{b''}\) (these must intersect \(X_b\) as well, by the properties of the tree decomposition.)

After replacing S with R, the number of components of the third type will not change, since it is the number of blocks in \(\mathcal {P}\). The components of the second type (and their number) will not change at all. On the other hand, the number of components of the first type will increase because of the assumption on \(R'\). Thus \(c(G_b-S)<c(G_b-R)\) holds, a contradiction. \(\square \)

Informally, the above claim shows that we can optimize separately on the two sides as long as we keep the same parameters. Notice, however, that it is possible that the partition induced by \(C(G_{b'}-S')\) is not \(\mathcal {P}\), but a proper refinement \(\mathcal {P}\sqsubset \mathcal {P'}\). (It must be a refinement since \(G_b-S\) contains more vertices and edges, which can only decrease the number of components.) In this case, a similar argument shows that we can still replace \(S'\) with some \(R'\) that gives more components if \(R'\) matches the same parameters as \(S'\), i.e., \(R'\cap X_b=Q\) and \(C(G_{b'}-R')\) induces the partition \(\mathcal {P'}\) in \(X_b\). It is important to note that \(c(G_{b'}-R')\) is the number of blocks in \(\mathcal {P'}\), which is larger than the number of blocks in \(\mathcal {P}\). This means that, in \(G_b\), the edges of \(G_{b''}\) will connect some components of \(C(G_{b'}-R')\). However, the same components will be connected as in \(C(G_{b'}-S')\).

Now let \(S', S''\) be arbitrary cutting-sets of \(G_{b'}\) and \(G_{b''}\) satisfying \(S'\cap X_b=S''\cap X_b=Q\). Let \(\mathcal {P'}\) and \(\mathcal {P''}\) denote the partitions induced by \(C(G_{b'}-S')\) and \(C(G_{b''}-S'')\) on \(X_b\). Consider the components of \(G_b-(S'\cup S'')\). Any component that does not intersect \(X_b\) is the same as in \(C(G_{b'}-S')\) and \(C(G_{b''}-S'')\). On the other hand, some components of \(C(G_{b'}-S')\) may be joined by the edges of components of \(C(G_{b''}-S'')\), and vice versa. Nevertheless, it is clear that these components induce the partition \(\mathcal {P'}\sqcup \mathcal {P''}\) on \(X_b\).

The above argument implies that if we change \(S'\) to an \(R'\) that gives more components in \(G_{b'}\), matches the parameters Q and \(\mathcal {R'}\) such that \(\mathcal {R'}\sqcup \mathcal {P''}=\mathcal {P'}\sqcup \mathcal {P''}\), then we obtain more components in \(G_b-(R'\cup S'')\). Now we can also change \(S''\) to a better \(R''\) in a similar manner as long as \(\mathcal {R'}\sqcup \mathcal {R''}=\mathcal {P'}\sqcup \mathcal {P''}\).

\(c(G_b-(R'\cup R''))\) can be calculated in the following way. There are \(|\mathcal {R'}|\) (\(|\mathcal {R''}|\)) components in \(G_{b'}-R'\) (\(G_{b''}-R''\)) that intersect \(X_b\), and \(|\mathcal {R'}\sqcup \mathcal {R''}|\) components in \(G_b-(R'\cup R'')\) that intersect \(X_b\). The other components do not change, so

$$\begin{aligned} c(G_b-(R'\cup R''))= c(G_b-R')+c(G_b-R'')-|\mathcal {R'}|-|\mathcal {R''}|+|\mathcal {R'}\sqcup \mathcal {R''}|. \end{aligned}$$

These leads to the following claim.

Claim

$$\begin{aligned} {\textsc {Mnc}}(b,s,Q,\mathcal {P})&=\\&\max \left\{ \begin{array}{l} {\textsc {Mnc}}(b',s',Q,\mathcal {P'})\\ +{\textsc {Mnc}}(b'',s'',Q,\mathcal {P''})\\ -|\mathcal {P'}|-|\mathcal {P''}|+|\mathcal {P'}\sqcup \mathcal {P''}| \end{array} \left| \begin{array}{l} s'+s''-|Q|=s;\\ \mathcal {P'}\sqcup \mathcal {P''}=\mathcal {P};\\ {\textsc {Mnc}}(b,s',Q,\mathcal {P'})>0;\\ {\textsc {Mnc}}(b,s'',Q,\mathcal {P''})>0 \end{array} \right. \right\} . \end{aligned}$$

Proof

First, suppose that S is a cutting-set matching the parameters \(s, Q, \mathcal {P}\), and maximizes \(c(G_b-S)\). Let \(S'=S\cap V_{b'}\), \(S''=S\cap V_{b''}\), \(s'=|S'|\), \(s''=|S''|\), and let \(\mathcal {P'}\) (resp. \(\mathcal {P''}\)) be the partition that \(C(G_{b'}-S')\) (resp. \(C(G_{b''}-S'')\)) induced on \(X_b\). Now \(S'\) clearly matches the parameters \(b', s', Q, \mathcal {P'}\), and Claim 3 implies that it is optimal in \(G_{b'}\), thus \(c(G_{b'}-S')={\textsc {Mnc}}(b',s',Q,\mathcal {P'})\). Similarly, \(c(G_{b''}-S'')={\textsc {Mnc}}(b'',s'',Q,\mathcal {P''})\). We have already seen that \(c(G_b-S)\) is as given in the formula and that the conditions on the right side of the formula are all satisfied. (Notice that if for example \(S'=Q\) then \(s'\) and \(\mathcal {P'}\) are defined, so \({\textsc {Mnc}}(b',s',Q,\mathcal {P'})\) is defined, thus it is not 0.) This proves that \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) cannot be greater than the maximum on the right side.

On the other hand, suppose \(S'\) and \(S''\) are chosen so that all conditions on the right side are satisfied, then \(S=S'\cup S''\) will match the parameters \(b, s, Q, \mathcal {P}\), and the number of components in \(G_b-S\) is given by the formula in the maximum. This proves that \({\textsc {Mnc}}(b,s,Q,\mathcal {P})\) cannot be less than the maximum on the right side. \(\square \)

It remains to give a bound for the running time. The natural idea is that for fixed \(s, Q,\mathcal {P}\) values, we list all compatible values of \(s',s'', \mathcal {P'}, \mathcal {P''}\). The number of possible \(s',s''\) pairs is not more than |V(G)|; these are easy to list. However, after fixing \(s'\) and \(s''\), it is not easy to find all suitable partitions \(\mathcal {P''}\) for a given partition \(\mathcal {P'}\) (i.e. \(\mathcal {P'}\sqcup \mathcal {P''}=\mathcal {P}\) must hold).

So instead, for given \(s',s''\), we list all possible combinations of sets Q and \(\mathcal {P'}, \mathcal {P''}\) pairs of partitions of \(X_b-Q\). For \(\mathcal {P'}, \mathcal {P''}\) pair it is easy to compute \(\mathcal {P'}\sqcup \mathcal {P''}\). So the value obtained from the given combination \(s',s'',\mathcal {P'}, \mathcal {P''}\) is taken into consideration in the maximum to compute \({\textsc {Mnc}}(b,s'+s''-|Q|,Q,\mathcal {P'}\sqcup \mathcal {P''})\). Since the number of possible combinations of pairs \(Q, \mathcal {P'}\) and pairs \(Q,\mathcal {P''}\) is bounded by \({\mathcal {O}}(\textrm{tw}(G)^{\textrm{tw}(G)})\) (see the proof of Lemma 1), the total running time is bounded by \({\mathcal {O}}( |V(G)|\cdot \textrm{tw}(G)^{2\textrm{tw}(G)})\).

Theorem 8

There exists an algorithm to compute the toughness of a graph G with running time \({\mathcal {O}}\left( |V(G)|^3\cdot \textrm{tw}(G)^{2\textrm{tw}(G)}\right) \).

Proof

The number of nodes in \(\mathcal {T}\) is \({\mathcal {O}}(|V(G)|)\). Lemma 1 implies that the total size of information for one node of \(\mathcal {T}\) is \({\mathcal {O}}\left( |V(G)|\cdot \textrm{tw}(G)^{\textrm{tw}(G)}\right) \). Lemmas 2, 3, 4 and 5 show that all the information for leaf, forget and introduce nodes can be computed in

  • \({\mathcal {O}}\left( |V(G)|\cdot \textrm{tw}(G)^{\textrm{tw}(G)}\right) \) time for leaf nodes,

  • \({\mathcal {O}}\left( |V(G)|\cdot \textrm{tw}(G)^{\textrm{tw}(G)+1}\right) \) time for forget nodes,

  • \({\mathcal {O}}\left( |V(G)|\cdot \textrm{tw}(G)^{2\textrm{tw}(G)}\right) \) time for introduce nodes and

  • \({\mathcal {O}}\left( |V(G)|^2\cdot \textrm{tw}(G)^{2\textrm{tw}(G)}\right) \) time for join nodes.

The sum of these for each node together with the computation required at the end for the root is bounded by \({\mathcal {O}}\left( |V(G)|^3\cdot \textrm{tw}(G)^{2\textrm{tw}(G)}\right) \). \(\square \)

Corollary 1

The toughness can be computed in polynomial time for graphs with bounded treewidth.

Corollary 2

Toughness is Fixed Parameter Tractable parameterized with treewidth.

After presenting the above results at a conference, we were informed [16] that the results in [13] also imply an FPT algorithm parameterized by the treewidth or the clickwidth to compute the toughness. However, we believe that the running time of our algorithm is better both in the dependence on the number of vertices and the treewidth. Also, in our opinion our algorithm is easier to follow.

It is an open question whether there exist a faster algorithm with time bound \({\mathcal {O}}\left( |V(G)|^3\cdot c^{{\mathcal {O}}(\textrm{tw}(G))} \right) \) for some constant c, as for many similar problems in the literature. It seems that the known techniques do not work for toughness. For some other similar problems, it is proven that no such algorithm exists under the Exponential Time Hypothesis. Unfortunately, these techniques does not seem to work either. So finding a better algorithm or proving that it does not exists looks to be a challenging open problem.