1 Introduction
The classical 0–1 knapsack problem is an \(\mathcal{NP}\)-hard discrete optimization problem known to be relatively easy to solve in practice. This pleasant behavior usually changes as soon as additional constraints are imposed in addition to the standard weight constraint. In this paper we consider disjunctive constraints on pairs of items as a structurally simple but highly relevant class of conditions. In particular, we will study the following two types of restrictions:It is natural to represent these conflict and forcing constraints by means of an undirected graph \(G=(V,E)\) with \(|V|=n\) and \(|E|=m\), where each vertex corresponds uniquely to one item and an edge \((i,j) \in E\) indicates that items i and j are in a conflict (resp. forcing) relation.
-
A conflict constraint (negative disjunctive constraint) on a pair of items expresses an incompatibility between these items. For each conflicting pair, at most one item can occur in a feasible knapsack solution.
-
A forcing constraint (positive disjunctive constraint) enforces that at least one item from the underlying pair of items has to be included in a feasible solution.
Introducing the standard knapsack problem KP with n items, each of them with profit \(p_j\) and weight \(w_j\), \(j=1,\ldots ,n\), and a knapsack capacity c [cf. Kellerer et al. (2004)], we obtain the knapsack problem with conflict graph (KCG) by imposing the above conflict constraints on the solution of KP.
It is sometimes also referred to as disjunctively constrained knapsack problem, e.g. in the first paper dealing with KCG due to Yamada et al. (2002) where a branch-and-bound algorithm was presented. For more recent work on exact algorithms and heuristics for KCG see Hifi and Otmani (2012) and Hifi et al. (2014) and the references therein.
$$\begin{aligned} (KCG)\quad&\max&\sum _{j=1}^{n}p_{j}x_{j}\end{aligned}$$
(1)
$$\begin{aligned}&\text{ s.t. }&\sum _{j=1}^{n}w_{j}x_{j}\le c \end{aligned}$$
(2)
$$\begin{aligned}&x_{i}+x_{j}\le 1 \quad \forall \, \ (i,j)\in E \end{aligned}$$
(3)
$$\begin{aligned}&x_{j}\in \{0,1\} \quad j=1,\ldots ,n. \end{aligned}$$
(4)
Anzeige
Conflict graphs were also considered for many other combinatorial optimization problems such as bin packing [see e.g. Muritiba et al. (2010); Sadykov and Vanderbeck (2013)], scheduling problems [see e.g. Even et al. (2009)]. Recently, positive and negative disjunctive constraints were considered for minimum spanning tree, matching and shortest path in Darmann et al. (2011), for matching in Öncan et al. (2013), for minimum spanning tree in Zhang et al. (2011) and for the maximum flow problem in Pferschy and Schauer (2013).
A related problem is the knapsack problem with forcing graph (KFG) which was, to the best of our knowledge, not considered in the literature before. Given a forcing graph \(G=(V,E)\) it follows from KCG by replacing (3) byWe can also take a different view at these two problems from a graph theoretic perspective. Clearly, KCG is equivalent to a maximum weight independent set problem (MWIS) maximizing the sum of \(p_j\) when an additional weight constraint imposed. MWIS is known as a famous \(\mathcal{NP}\)-hard problem and even hard to approximate within a factor of \(n^{1-\varepsilon }\) even in the unweighted case with \(p_j=1\) [Håstad (1999)].
$$\begin{aligned} x_{i}+x_{j}\ge 1 \quad \forall \, \ (i,j)\in E . \end{aligned}$$
(5)
A large body of literature exists for identifying special graph classes where MWIS is still polynomially solvable or allows a positive approximation result. In this paper we will proceed in the same direction for KCG, i.e. for MWIS with a budget constraint.
Problem KFG is closely related to a minimum weight vertex cover problem but with a different objective function. We will come back to this relation in Sect. 5. For the minimum weight vertex cover problem it is known that no PTAS exists, but various papers study the approximability on special graph classes. Both independent set and vertex cover are polynomially solvable on perfect graphs. In contrast, it can be shown that both KCG and KFG are strongly \(\mathcal{NP}\)-hard for perfect graphs.
Anzeige
Because of this inherent difficulty of KCG and KFG we concentrate in this paper on the identification of special graph classes as conflict (resp. forcing) graphs to derive positive approximation results. In Pferschy and Schauer (2009) we derived FPTASs for KCG on graphs of bounded treewidth and on chordal graphs. These are both based on tree structures representing the graph G and dynamic programming. In this paper we make considerable progress by applying much more complicated methods to derive approximation results for larger graph classes.
The contributions of this paper are the following:Table 1 gives an overview of our main results for KCG and KFG
1.
An important generalization of chordal graphs are weakly chordal graphs. It will be shown in Sect. 2 that KCG still permits an FPTAS on weakly chordal graphs (and more generally on all graphs whose relevant potential maximal cliques can be listed in polynomial time, e.g. \(P_5\)-free graphs). The underlying technique of this construction was developed by Fomin and Villanger (2010). It was expanded by Lokshtanov et al. (2014) who recently gave a polynomial time algorithm for the weighted independent set problem on \(P_5\)-free graphs. Note that this technique is crucial for KCG on weakly chordal graphs since it allows dynamic programming.
2.
A general algorithmic strategy for solving difficult optimization problems on graphs is graph decomposition. A frequently applied pattern (see e.g. the extensive work by Brandstädt and co-authors) applies modular decomposition followed by clique decomposition to break down the graph into much smaller and sometimes “benevolent” subgraphs. In fact, there are a number of graph classes for which special structural properties of the resulting atoms of prime graphs are known. We will show in Sect. 3 that KCG allows an FPTAS on any graph for which the atoms of its prime components allow an FTPAS. A number of examples for such graph classes is described in Sect. 3.3.
3.
It is well known that planar graphs allow positive approximation results for vertex cover and independent set. Therefore, planar graphs are obvious candidates for seeking further positive results for disjunctively constrained knapsack problems. Indeed, we show in Sect. 4 that KCG allows a PTAS (but not an FPTAS) for H-minor free conflict graphs. We will more generally show that a result of Demaine et al. (2005) can be expanded to guarantee PTASs for a more general class of graph problems. This result includes KCG on graphs of bounded genus.
4.
Considering FCG in Sect. 5 it turns out that all results for an FPTAS carry over from KCG to KFG by means of a simple transformation. Interestingly, this analogy breaks down for planar graphs: In fact, even finding a feasible solution for KFG on planar graphs is strongly \(\mathcal{NP}\)-complete while there exists a PTAS for KCG.
Table 1
Complexity results for KCG and KFG on special graph classes
Graph class |
KCG
|
KFG
|
|---|---|---|
General | Strongly \(\mathcal{NP}\)-hard | Feasibility \(\mathcal{NP}\)-complete |
Bounded treewidth | FPTAS | FPTAS |
Chordal | FPTAS | FPTAS |
Weakly chordal | FPTAS | FPTAS |
Planar | PTAS, no FPTAS | Feasibility \(\mathcal{NP}\)-complete |
Perfect | Strongly \(\mathcal{NP}\)-hard | Strongly \(\mathcal{NP}\)-hard |
1.1 Basic definitions
In this section we give some definitions and concepts that are used throughout the paper. Mostly, we stick to standard notation as it is used in textbooks such as Diestel (2012).
Definition
Upper bound Throughout the paper we will frequently require an upper bound on the objective function value (1). While for practical applications the quality of an upper bound is crucial, a trivial bound of \(P:=\sum _{j=1}^n p_j\) suffices for our theoretical results.
Definition
Neighborhood For a given subset of vertices A, the neighborhood N[A] contains A and all vertices adjacent to at least one vertex in A (analogous for a single vertex v we have N[v]) and \(N(A) := N[A] \setminus A\).
Definition
ab-separator
A set of vertices \(V' \subset V\) is called ab-separator if the vertices a and b belonging to the same connected component of G are in different components of \(G\setminus V'\).
Definition
Separator
A set \(V' \subset V\) is a separator if there are vertices a and b in G such that \(V'\) is an ab-separator. A separator \(V'\) is a minimal ab-separator if any proper subset of \(V'\) is not an ab-separator in G. A separator \(V'\) is a minimal separator if there are vertices a and b in G such that \(V'\) is a minimal ab-separator.
Definition
Tree-decomposition [cf.Diestel (2012), Sec. 12]
Let \(G=(V,E)\) be a graph, T a tree, and let \(\mathcal {V}=(V_{I})_{I\in V(T)}\) be a family of vertex sets \(V_{I}\subseteq V(G)\) indexed by the vertices I of T. By capital letters we refer to vertices from T, whereas by lower case letters we refer to vertices from G. The pair \((T,\mathcal {V})\) is called a tree-decomposition if it satisfies the following three properties:
1.
\(V(G)=\bigcup _{I\in T}V_{I}\);
2.
for every edge \(e\in G\) there exists \(I\in T\) such that both ends of e lie in \(V_{I}\);
3.
\(V_{I_{1}}\cap V_{I_{3}}\subseteq V_{I_{2}}\) whenever \(I_{2}\) lies on the path from \(I_{1}\) to \(I_{3}\) in T.
Definition
Treewidth
The width of \((T,\mathcal {V})\) is defined as \(\max \{|V_{I}|-1 \mid I\in T\}\). The treewidth of G is the smallest width of any tree-decomposition of G.
Note that deciding whether a tree-decomposition of treewidth at most k exists, and if so, finding such a tree-decomposition (for constant k) can be done in linear time [cf. Bodlaender and Koster (2008)].
Definition
Graphs having a property nearly [cf. Brandstädt and Hoàng (2007)]
For a given graph property \(\mathcal P\) a graph is nearly
\(\mathcal{P}\), if for all vertices v of G the graph induced by V without the neigborhood of v, i.e. \(G[V\setminus N(v)]\), fulfills \(\mathcal P\).
For KCG it is easy to see that any pseudopolynomial algorithm for graphs with property \(\mathcal P\) will trivially imply a pseudopolynomial algorithm for nearly \(\mathcal P\) graphs. It suffices to go through all vertices v and determine the best solution including v. Such a solution consists of the best solution which is compatible with v, i.e. the optimal solution of KCG for capacity \(c-w(v)\) on \(G[V\setminus N[v]]\), which can be computed in pseudopolynomial time by assumption.
As an example for the above argument, it follows immediately from Pferschy and Schauer (2009) that KCG allows a pseudopolynomial algorithm and also an FPTAS for nearly chordal graphs.
The next definition is a variant of the more general definition that can be found in Pruhs and Woeginger (2007).
Definition
Subset selection problem
A subset selection problem is defined by a ground set X with n elements each of which has associated a positive profit p(x) for \(x \in X\) and for each subset Y of X it can be decided in polynomial time whether Y is feasible. Moreover assume that every instance of the subset selection problem has a feasible solution. Then we are looking for a feasible subset of X with maximum total profit.
The following general result about the existence of an FPTAS based on a given pseudopolynomial algorithm will be applied frequently throughout this paper.
Theorem 1
[Pruhs and Woeginger (2007)] If there exists an exact algorithm for a subset selection problem with running time polynomial in n and in \(\sum _{x\in X} p(x)\) then there exists also an FPTAS for this problem.
It is easy to see that KCG belongs to this family of subset selection problems. Note that it is trivial to find a feasible solution for KCG (take the empty set or any single item as a solution). However, for KFG on a general forcing graph it is strongly \(\mathcal{NP}\)-complete to determine even the existence of a feasible solution: Indeed, given an arbitrary instance of the minimum vertex cover problem, one could define an instance of KFG on the same graph with all item weights equal to one. Then there exists a vertex cover of size at most c iff KFG with capacity c has a feasible solution.
However, the vertex cover problem is polynomially solvable on all graph classes for which we apply Theorem 1 in this paper. Thus, one can check the feasibility of an instance in a preprocessing step and restrict KFG to instances with a feasible solution.
2 Weakly chordal conflict graphs
The main goal of this section is to derive an FPTAS for KCG on weakly chordal graphs, which are a well studied superclass of chordal graphs [e.g. Cameron et al. (2003); Hayward et al. (2007)]. It is known that weakly chordal graphs are perfect.
A hole is an induced cycle with five (i.e. a \(C_5\)) or more vertices and an anti-hole is the complement of a hole. A graph is chordal (also known as triangulated graph) if it contains neither induced holes nor a \(C_4\). In other words, any cycle with more than three vertices must contain a chord. A graph is weakly chordal if it does not contain induced holes and anti-holes.
The weighted independent set problem was polynomially solved on weakly chordal graphs by Hayward et al. (1989). Their algorithm was later improved by Spinrad and Sritharan (1995). However these algorithms cannot be adopted to solve the knapsack problem with conflicts: They perform a sequence of iterations to transform the given weakly chordal graph into intermediate graphs, which are all weakly chordal, until finally a clique is obtained. In every transformation step the weight of the maximum weight independent set of the involved graphs stays the same. Unfortunately the algorithms modify non-optimal independent sets which might represent optimal solution sets in the disjunctively constrained knapsack problem.
As usual we define a triangulation of a graph \(G=(V,E)\) as a chordal supergraph \(G'=(V,E \cup E')\) of G, where the edges from \(E'\) are called fill edges. A minimal triangulation of G is a triangulation \(G'\) such that removing any edge from \(E'\) results in a non-chordal graph. If there exists a minimal triangulation \(G'\) such that \(V'\subseteq V\) induces a maximal clique in \(G'\), then \(V'\) is called a potential maximal clique.
Bouchitté and Todinca (2002) proved that all potential maximal cliques of a graph can be generated in time that is polynomial in the number of minimal separators of a graph. Moreover Bouchitté and Todinca (2001) proved that weakly chordal graphs contain polynomially many minimal separators. Combining these results leads to the well known result that weakly chordal graphs contain only a polynomial number of potential maximal cliques.
Fomin and Villanger (2010) gave an algorithm that finds large induced subgraphs of bounded treewidth of a graph G which contains only polynomially many potential maximal cliques. Noting that an independent set has treewidth 0, Lokshtanov et al. (2014) showed that the algorithm given by Fomin and Villanger (2010) can be modified in order to solve the weighted independent set problem.
Theorem 2
[Lokshtanov et al. (2014), Proposition1] There is an algorithm that given as input a vertex weighted graph G on n vertices and m edges, together with a list \(\Pi \) of potential maximal cliques, outputs in time \(O(|\Pi |n^5 m)\) the weight of the maximum weight independent set I such that there exists a minimal triangulation H of G such that every maximal clique C of H is on the list \(\Pi \) and satisfies \(|C \cap I| \le 1\).
Fomin and Villanger (2010) use minimal triangulations in their dynamic program, whereas Lokshtanov et al. (2014) use a special tree-decomposition which is related to the clique tree of a minimal triangulation. We recapitulate their main definitions and technical prerequisites: let I be an independent set in G. An I-good minimal triangulation is a minimal triangulation of G such that no vertex of I is incident to a fill edge. A tree-decomposition \((T,\mathcal {X})\) of G is called I-sparse if each bag \(B \in \mathcal {X}\) contains at most one vertex from I (i.e. \(|I \cap B| \le 1\)). A rooted tree-decomposition is simple if no bag B is a subset of any other bag \(B'\) and for every \(u, v \in V(T)\) where v is a descendant of u in T, there exists a component \(C \in C(\mathcal {X}(u))\) such that \(\mathcal {X}(v) \subset \mathcal {X}(u) \cup C\).
The connection between minimal triangulations and simple tree-decompositions was established by Lokshtanov et al. (2014). They proved that every minimal triangulation has a clique tree that is a simple tree-decomposition and on the other hand that any simple tree-decomposition of G, whose bags are potential maximal cliques of G, is a clique tree of a minimal triangulation H of G.
Moreover, they proved that for every independent set I in G there exists a minimal triangulation which is I-good. With the above statement it follows that for such an I-good minimal triangulation there always exists an I-sparse simple tree-decomposition since all bags of the tree-decomposition are maximal cliques of the triangulation. Thus, the following Theorem 3 (quoted from the original source) outputs an independent set I which solves the weighted independent set problem on G if a complete list of all potential maximal cliques is given.
Theorem 3
[Lokshtanov et al. (2014), Lemma 16] There is an algorithm that given as input a vertex weighted graph G on n vertices and m edges, together with a list \(\Pi \) of potential maximal cliques of G, outputs in time \(O(|\Pi |^2 n^4 m)\) the weight of the maximum weight independent set I such that there exists an I-sparse simple tree-decomposition \((T, \mathcal {X})\) of G such that \(\mathcal {X}(v) \in \Pi \) for all \(v \in V(T)\). If no such independent set exists, the algorithm outputs \( - \infty \).
Note that due to the different techniques used, Theorem 2 provides a better running time than the algorithm of Theorem 3. Due to the more accessible technique we decided to follow the approach presented in Lokshtanov et al. (2014) and solve KCG by dynamic programming over tree-decompositions on all graph classes whose potential maximal cliques can be listed in polynomial time.
Let B be a potential maximal clique from the set \(\Pi \) of all potential maximal cliques. We look at B as a graph separator and denote by \(\mathcal {C}_B=\{C_B^1, \ldots , C_B^{k_B}\}\) the set of all connected components of \(G\setminus B\). The indices \(1, \ldots ,k_B\) are assigned according to the size of the components with \(|C_B^i| \le |C_B^{i+1}|\) and ties are broken arbitrarily. Let \(K_B^j = \bigcup _{i=1}^j C_B^i\) denote the partial union of components. A restriction of the set of components to those which are fully contained in some given set \(X\subseteq V\) is denoted by \(\mathcal {C}_B(X) = \{C \in \mathcal {C}_B \mid C \subseteq X \}\). The elements of \(\mathcal {C}_B(X)\) are ordered according to indices given to the elements of \(\mathcal {C}_B\): If \(\mathcal {C}_B(X)=\{C_B^1(X), C_B^2(X), \ldots , C_B^{k_B(X)}(X)\}\), this means that two sets \(C_B^i(X)\), \(C_B^{i+1}(X)\) correspond to sets \(C_B^{i'}\) and \(C_B^{j'}\) from \(\mathcal {C}_B\) with \(i'<j'\). Note that this ordering is not strictly necessary for the correctness of the described method but avoids recursive evaluations. Again, the partial union is defined as \(K_B^j(X) = \bigcup _{i=1}^j C_B^i(X)\).
In the following we proceed along the lines and notation layed out in Lokshtanov et al. (2014). However, our approach is more complicated since it does not suffice to collect “large” independent sets from subgraphs but the weight and profit values of any possible subset of the solution has to be kept explicitly for further consideration.
We will introduce a dynamic programming function \(M=M(B,S,K_B^j(X),p)\) which takes as arguments a potential maximal clique \(B \in \Pi \), a set \(S\subseteq B\) which contains either a single vertex of B or is empty (S represents the potential inclusion of the associated item into the solution), a partial union \(K_B^j(X)\) of components separated by B according to the above definition for some restricting set \(X\subseteq V\), and finally a profit value \(p \in \{0,1,2,\ldots , P\}\). M is now a function that returns the weight of the minimum weight independent set \(I \subseteq B \cup K_B^j(X)\) with a profit of \(p + p(S)\) such that \(I \cap B = S\) and the following property of a tree-decomposition: There exists an I-sparse simple tree-decomposition \((T, \mathcal {X})\) of \(G[B \cup K_B^j(X)]\) such that all bags of \((T, \mathcal {X})\) are potential maximal cliques and B is the root vertex of T. If no such I exists, then M returns \(\infty \).
Now we construct a recursion to determine the values of M as follows. For a certain potential maximal clique \(B \in \Pi \), a single candidate vertex represented by S and some restricting set X we consider the components \(\mathcal {C}_B(X)\) resulting from the separation by B in increasing order of their size and add them one after the other. In the iteration appending component \(C_B^j(X)\) we split the target profit value p into a part \(p'\) contributed by vertices (compatible with S) from previous components \(C_B^1(X), \ldots , C_B^{j-1}(X)\) which is already summarized in \(K_B^{j-1}(X)\) [see (6)] and the complementing part \(p-p'\) contributed by vertices in \(C_B^{j}(X)\). So we can split the independent set I corresponding to the optimal value of \(M(B,S,K_B^j(X),p)\) into parts \(I_1, \ldots , I_j\) where \(I_i:= (I \cap C_B^i(X)) \setminus S\).
The difficult part arises from considering the connection between \(C_B^{j}(X)\) and the separator B. To allow a recursive evaluation we have to separate also \(C_B^{j}(X)\). To do so, we go through all potential maximal cliques \(B' \in \Pi \) which may serve as a “connector” between B and the components of \(C_B^{j}(X)\) arising from a separation by \(B'\) [see (7)]. At the same time the inclusion of the vertex represented by S has to be kept feasible also w.r.t. \(C_B^{j}(X)\) and the existence of the required tree-decomposition has to be kept alive.
This leads to a minimization over all potential maximal cliques \(B' \in \Pi \) and all subsets \(S'\) fulfilling the following properties: (a) \(B' \subseteq B \cup C_B^{j}(X)\), (b) \(N(C_B^{j}(X)) \subseteq B'\), (c) \(B' \cap C_B^{j}(X) \ne \emptyset \), (d) \(|S'| \le 1\), (e) \(B \cap B' \cap S = B \cap B' \cap S'\), (f) \(G[S \cup S']\) is independent.
(a)–(c) imply that \(B'\) serves as a “connector” between B and \(C_B^{j}(X)\) whereas (e) and (f) state the compatibility of S and \(S'\). In fact, for \(|S|=1\) they only allow the following two cases: Either \(S=S'\) or (if both are non-empty) S is not in \(B'\), \(S'\) is not in B and the corresponding vertices are not adjacent.
With these preliminaries we now state the crucial recursion1.
The initialization for the first component, i.e. \(K_B^1(X)=C_B^1(X)\), is defined in the following way:
$$\begin{aligned} M\left( B,S,K_B^j(X),p \right)&= w(S) + \min _{p'\le p} \bigg \{ M\left( B,S,K_B^{j-1}(X),p'\right) - w(S) + \end{aligned}$$
(6)
$$\begin{aligned}&\quad + \min _{\{B',S' \mid (p-p'-p(S'\setminus S)) \ge 0 \}} \Big \{ w(S' \setminus S) + \end{aligned}$$
(7)
$$\begin{aligned}&\quad + M\left( B',S',K_{B'}^{k_{B'}(\cdot )}(C_B^j(X)),p-p'-p(S'\setminus S)\right) - w(S')\Big \} \bigg \} \\&\text{ where } B', S' \text{ fulfill } \text{(a)--(f) } \nonumber \end{aligned}$$
(8)
$$\begin{aligned} M\left( B,S,K_B^1(X),p \right)&= w(S) + \min _{\{B',S' \mid ( p-p(S'\setminus S)) \ge 0\}}\Big \{ w(S' \setminus S) + \\&\quad + M\left( B',S',K_{B'}^{k_{B'}(\cdot )}(C_B^1(X)),p-p(S'\setminus S)\right) - w(S')\Big \} \bigg \}\nonumber \\&\text{ where } B', S' \text{ fulfill } \text{(a)--(f) } \nonumber \end{aligned}$$
(9)
Lemma 4
Proof
“\(\le \)”
For the three parameters \(p'\), \(B'\) and \(S'\) that minimize the right hand side of (6)–(8), \(I_j\) is the independent set of \(G[C_B^j(X) \cup B']\) consuming a weight ofand \(I'\) the independent set of \(G[B\cup K_B^{j-1}(X)]\) consuming a weight of(if they exist). If one of these weight values is \(\infty \) we are done. We now have to show that \(I:=I_j \cup I'\) is independent and that there exists an I-sparse simple tree-decomposition \((T, \mathcal {X})\) of \(G[B \cup K_B^j(X)]\) such that all bags of \((T, \mathcal {X})\) are potential maximal cliques and B is the root vertex of T. All pairs of vertices from \(K_B^{j-1}(X)\) and \(C_B^j(X)\) are independent since they are separated by vertices from B. If \(I_j\) contains a vertex from B then by property (e) it must be the vertex in S, hence I is independent. We also know that there exists an \(I_j\)-sparse simple tree-decomposition \((T_j, \mathcal {X}_j)\) of \(G[C_B^j(X) \cup B']\) such that all bags of \((T_j, \mathcal {X}_j)\) are potential maximal cliques and \(B'\) is the root vertex of \(T_j\). There also exists an \(I'\)-sparse simple tree-decomposition \((T', \mathcal {X}')\) of \(G[B\cup K_B^{j-1}(X)]\) such that all bags of \((T', \mathcal {X}')\) are potential maximal cliques and B is the root vertex of T. We will now merge these two decompositions into a simple tree-decomposition \((T, \mathcal {X})\) of \(G[B \cup K_B^j(X)]\), where \(\mathcal {X}=\mathcal {X'} \cup \mathcal {X}_j\): the new tree structure T results from adding the edge \((B,B')\) to the disjoint union of \(T_j\) and \(T'\). \((T, \mathcal {X})\) is a tree decomposition because of property (b). It is I-sparse because of the respective sparseness of \((T', \mathcal {X}')\) and \((T_j, \mathcal {X}_j)\) and property (e). Moreover, it is simple because both tree-decompositions are simple and property (a) and (c). Hence \(M\left( B,S,K_B^j(X),p \right) \le p(I)\).
$$\begin{aligned} M\left( B',S',K_{B'}^{k_{B'}(\cdot )}(C_B^j(X)),p-p'-p(S'\setminus S)\right) \end{aligned}$$
$$\begin{aligned} M\left( B,S,K_B^{j-1}(X),p'\right) \end{aligned}$$
“\(\ge \)”
Let I be an independent set of \(G[B \cup K_B^j(X)]\) of weight \(M\left( B,S,K_B^j(X),p \right) \) such that \(I\cap B = S\) and \((T, \mathcal {X})\) is an I-sparse simple tree-decomposition of \(G[B \cup K_B^j(X)]\) with root bag B, i.e. \(\mathcal {X}(r(T)) = B\). For \(C_B^j(X)\) there is exactly one child vertex \(V_j\in T\) of r(T) with \(\mathcal {X}(V_j) \cap C_B^j(X) \ne \emptyset \): if there exists another child \(V_j'\) of r(T) such that \(\mathcal {X}(V_j')\) has a nonempty intersection with \(C_B^j(X)\) we get that also B has to contain an element of \(C_B^j(X)\): since \((T, \mathcal {X})\) is a tree-decomposition all vertices of bags of the sub tree-decomposition rooted in \(V_j\) are separated by B from all vertices of bags of the sub tree-decomposition rooted in \(V_j'\).
Denote \(\mathcal {X}(V_j)\) as \(B'\) and \(I \cap B'\) as \(S'\). These two sets obviously satisfy conditions (a) and (c)–(f). Assume that (b) is not satisfied and hence B contains an element v from \(N(C_B^j(X))\) which is not in \(B'\). Let \(w\in C_B^j(X)\) be a neighbor of v. Denote by \(U_1, \ldots , U_k\) all child vertices of \(V_j \in T\). We know that v is not in \(\mathcal {X}(U_i)\) for any i or in any of its childs since this would imply that it is also in B. Moreover, w is not in B, but this already gives a contradiction since there has to be a bag in T containing u and w.
Let \((T_j, \mathcal {X}_j)\) be the sub tree-decomposition of \((T, \mathcal {X})\) rooted in \(B'\) and \((T', \mathcal {X}')\) the tree-decomposition which results from \((T, \mathcal {X})\) by removing \((T_j, \mathcal {X}_j)\). Let \(I_j = I \cap (B' \cup C_B^j(X))\) and \(\bar{I} = I \setminus I_j\). Both \((T_j, \mathcal {X}_j)\) and \((T', \mathcal {X}')\) are simple because of the simplicity of \((T, \mathcal {X})\) and both are sparse because of the I-sparsity of \((T, \mathcal {X})\). Hence, \((T_j, \mathcal {X}_j)\) is an \(I_j\)-sparse simple tree-decomposition and \((T', \mathcal {X}')\) is an \(\bar{I}\)-sparse simple tree decomposition. It follows that \(I_j\) and \(\bar{I}\) can be chosen as independent sets on the left hand side of the equation and thus the “\(\ge \)” side of the equality follows. \(\square \)
Theorem 5
Given the complete list \(\Pi \) of all potential maximal cliques of G, KCG can be solved to optimality in time
$$\begin{aligned} O(|\Pi |^3 \cdot n^4 \cdot P^2). \end{aligned}$$
Proof
The structural results pointed out above can be utilized as follows: Lokshtanov et al. (2014) showed that any minimal triangulation of G has a clique tree which is a simple tree-decomposition of G. The bags of this tree-decomposition are potential maximal cliques of G by definition. On the other hand, any simple tree-decomposition, whose bags are potential maximal cliques of G, is a clique tree of a minimal triangulation of G.
Moreover, Lokshtanov et al. (2014) showed that for any independent set I in G, and thus also for an optimal solution \(I^*\) of KCG, there exists a minimal triangulation which is I-good. It follows that this triangulation has a clique tree which is a simple tree-decomposition and whose bags are potential maximal cliques of G. Clearly, this tree-decomposition is also I-sparse.
By evaluating function M we get among all potential maximal cliques B and all subsets S of cardinality \(\le 1\) the maximum profit \(p^*\) such that:This function value is attained for an independent set I with total weight \(\le c\), such that there exists an I-sparse simple tree-decomposition \((T, \mathcal {X})\) of G with bags \(\mathcal {X}(v) \in \Pi \) for all \(v \in V(T)\), as stated in Lemma 4. Clearly, this set I is a feasible solution for KCG.
$$\begin{aligned} M(B,S,K_B^{k_B}(V),p^* - p(S)) \le c \end{aligned}$$
By definition of M and the above consideration, the independent set \(I^*\) also contributes such a function value with weight \(\le c\) and profit \(p=p(I^*)\) for some input configuration. Thus, taking in M the maximum total profit over all such sets I will necessarily reach the maximum total profit \(p^*=p(I^*)\).
To achieve the stated running time complexity we apply a preprocessing step and calculate for all possible potential maximum cliques \(B\in \Pi \) all the O(n) components of \(\mathcal {C}(B)\), which can be done in \(O(|\Pi | (m+n))\) time by breadth first search. In a next step we check for all pairs of components whether one of them is a subset of the other and store the result in a containment matrix of size \(O(|\Pi |^2 n^2)\). Since each check can be done in linear time this takes all together \(O(|\Pi |^2 n^3)\) time. In the following we can use this information to check in constant time if a component is a subcomponent of another one.
Let us estimate the number of different argument tuples for M: There are \(|\Pi |\) different potential maximal cliques B each of them containing at most n subsets S with one item. The partial union \(K_B^j(X)\) is taken over \(k_B(X) \le n\) different values of j and each of them might be restricted by any of the \(|\Pi | n\) different components X. Multiplying these choices the number of different argument tuples for M can be roughly bounded byThe function M is now evaluated for each of these possible argument tuples. This is done by first sorting all \(|\Pi | n\) possible components in increasing order of size. Clearly, a component of minimum size cannot contain any of the other components properly. Hence, if a potential maximal clique B induces more than one, say i, components \(\in \mathcal {C}_B\) of minimum size we can easily compute \(M(B,S,K_{B}^{i}(C'),p)\) for all possible choices of \(C'\). If we now go to components of second smallest size we can compute all relevant tuples of M relying on the values calculated in the previous step. This process continues until we reach the components of largest size.
$$\begin{aligned} O(|\Pi | \cdot n \cdot n \cdot |\Pi | n \cdot P). \end{aligned}$$
Performing an evaluation of M for a certain tuple requires \(O(|\Pi | \cdot n \cdot P)\) values of previously calculated values of M. Hence we get a total running time of
\(\square \)
$$\begin{aligned} O(|\Pi | \cdot n \cdot n \cdot |\Pi | n \cdot P \cdot |\Pi | \cdot n \cdot P) =O(|\Pi |^3 \cdot n^4 \cdot P^2) \end{aligned}$$
Remark 1
The sorting of the components by their size is not really necessary. Alternatively, one could start the recursion \(M(B,S,K_B^{k_B(V)}(V),c - w(S))\) for all choices of B and S and store values of M with certain argument tuples when they are actually computed for the first time during a recursion. These stored values can then be used in other recursive calls in order to avoid calculating the function with the same tuple set more than once.
By Bouchitté and Todinca (2001) weakly chordal graphs have \(O(n^2)\) minimal separators which can be computed in \(O(n^5)\) time by Berry et al. (1999). By Bouchitté and Todinca (2002) the potential maximal cliques of any graph can be listed in \(O(n^2m|\Delta _G|^2)\), where \(\Delta _G\) is the set of all minimal separators of G. Hence we get the following corollary:
Corollary 6
KCG can be solved in \(O(n^{22} \cdot m^4 \cdot P^2)\) time on weakly chordal graphs.
It should be clear that this is only a very loose upper bound on the running time, but its improvement is not in the scope of this paper. By Theorem 1 we can state the main result of this section:
Corollary 7
There is an FPTAS for KCG on weakly chordal graphs.
Remark 2
The main result of Lokshtanov et al. (2014) was giving a polynomial time algorithm for the weighted independent set problem in \(P_5\)-free graphs. They showed that for this graph class a subset of all potential maximum cliques of polynomial size can be found in polynomial time that allows to find the maximum weight independent set. Note that the set of potential maximum cliques found by them also guarantees to find the optimal KCG solution when plugged into our algorithm.
We conclude that there exists an FPTAS for KCG on \(P_5\)-free graphs.
3 Modular decomposition and clique separators
In this section we consider graph decomposition techniques that were widely used in the literature for solving the (weighted) independent set problem on special graph classes.
A clique separator
C of a connected graph G is a separator (recall Sect. 1.1) which is a clique. By definition of a separator the graph \(G[V\setminus C]\) has \(\ell \) connected components \(A_1, A_2, \ldots , A_\ell \) with \(\ell \ge 2\).
A clique separator decomposition recursively separates \(G_1 =G [A_1 \cup C]\), \(G_2 = G[A_2\cup C],\ldots , G_\ell = G[A_\ell \cup C]\) by clique separators. Any subgraph not containing a separating clique is called atom. Following Tarjan (1985) the decomposition procedure can be represented by a clique decomposition tree, where each inner node represents a clique separator (as a set of vertices) and all leaves represent atoms (again as sets of vertices). It is important to note that the decomposition algorithm presented by Tarjan (1985) separates an atom in every step, i.e. in the resulting decomposition tree all inner nodes lie on a path.
Clique separator decomposition was applied frequently in the literature to solve \(\mathcal{NP}\)-hard problems on special graph classes. We will mention only the classical results by Tarjan (1985) and Whitesides (1984) for maximum clique and independent set on special graph classes such as chordal graphs, clique separable graphs and EPT-graphs.
A module of a graph G is a set of vertices M such that every vertex outside M is either connected to all vertices in M or to none of them. Informally speaking, all vertices in M “look the same” for vertices in \(G\setminus M\). Formally, for all \(v\in G\setminus M\) either \(N(v) \cap M = M\) or \(N(v) \cap M = \emptyset \). A module is non trivial if \(1<|M|<|V|\).
The concept of modular decomposition was introduced by Gallai (1967) and appears in the literature under different names, e.g. substitution decomposition in Möhring and Rademacher (1984). It was applied frequently for the solution of \(\mathcal{NP}\)-hard problems on special graph classes, e.g. by Lozin and Milanič (2008) for the solution of the maximum weight independent set on fork-free graphs.
Following Brandstädt and Hoàng (2007) a graph with non trivial module M can be decomposed in the following way: \(G_1 = G[M]\) and \(G_2 = G[(V \setminus M) \cup \{v_M\}]\) where \(v_M\) is a new vertex which has the same adjacencies in \(G[V\setminus M]\) as the module M. This means that \(G_1\) is the subgraph of G induced by M and \(G_2\) is a subgraph of G where the module M is removed and replaced by a single vertex \(v_M\). From a computational point of view, it makes sense to use only maximal modules. This avoids the iterative extension of a subset of a module in several decomposition steps and instead tackles the maximal module immediately in one step. If this process is applied recursively one gets a modular decomposition of the graph which can be represented by a decomposition tree \(\mathcal M\). Note that \(\mathcal M\) is a full binary tree, i.e. a tree where every node (with exception of the leaves) has exactly two child nodes. The leaves of \(\mathcal M\) correspond to subgraphs that cannot be further decomposed by non trivial modules. These graphs are called prime.
In the literature a slightly different decomposition process is frequently applied [cf. McConnell and Spinrad (1999)], where G is first partitioned into connected and co-connected components. Each of the resulting subgraphs can be partitioned into modules. However, to preserve the analogy to the clique decomposition we stick to the version described above with one module contracted in each step.
In this section we follow the approach of Brandstädt and Giakoumakis (2015) and apply both modular and clique decompositions. This means that we start with a modular decomposition which yields a collection of prime graphs. Then we apply clique decomposition to each of these prime graphs until we reach the atoms of these graphs. Note that the resulting atoms are not necessarily prime. The main contribution of this section is the following result.
Theorem 8
If KCG can be solved in pseudopolynomial time on the atoms of the prime graphs resulting from a modular decomposition of G, then KCG can also be solved in pseudopolynomial time on G.
Based on this theorem we can exploit results from the literature of the following type:
(i)Given a graph G with some property \(\mathcal {P}\), the modular decomposition yields prime graphs inheriting property \(\mathcal {P}\).(ii)Given a prime graph with property \(\mathcal {P}\), its atoms have property \(\mathcal {Q}\).
Now Theorem 8 states that if KCG can be solved in pseudopolynomial time on graphs with property \(\mathcal {Q}\), then KCG can be solved in pseudopolynomial time also on graphs with property \(\mathcal {P}\). The relevance of this statement lies in the fact that in many cases atoms of prime graphs allow much more restrictive properties than the original graph and thus pseudopolynomial results requiring a more restrictive property \(\mathcal {Q}\) can be extended to a wider family of graphs observing only a weaker property \(\mathcal {P}\). At the end of this section we will give a number of examples for graph properties \(\mathcal {P}\) which allow a pseudopolynomial solution of KCG through an application of Theorem 8. We will assume that any given pseudopolynomial algorithm returns not only a single optimal solution value but a full array of weight values for every target profit smaller than the given upper bound2.
In the following we will present a dynamic programming approach for KCG. During the decomposition approach subproblems will be solved and their optimal solutions contracted into single vertices. Therefore, we introduce the best solution obtained from including a single vertex v. This includes item v and possibly the solutions of subproblems previously merged into v. For every profit value p, \(0\le p \le P\), let \(d_p(v)\) be the minimum weight required for a feasible solution given by item v with total profit p. As an initialization we use \(d_{p_v}(v)= w_v\) and \(d_{p}(v)= \infty \) (or a large constant) for \(p\ne p_v\).
With this definition we only work with function values of d and never refer explicitly to profits and weights of individual items. In the beginning, d(v) contains only the feasible solution \(d_{p_v}(v)= w_v\) corresponding to the singleton solution \(\{v\}\). In the course of the computation more extensive solutions will be determined and their profits and weights inserted into d(v). The corresponding subgraphs of G will then be deleted and their information remains attached to v via d(v).
For a subset of vertices (items) \(V' \subseteq V\) we will also consider the optimal solution of KCG on \(G[V']\) derived either by recursion or by a direct algorithm available for graphs with a certain property. The corresponding solution values will be represented by a dynamic programming array, where \(z_p(V')\) gives the minimum weight of a feasible solution with profit p for KCG restricted to \(G[V']\). It is necessary to define \(z_0(V')=0\) as an empty solution.
3.1 Modular decomposition
Recall that every inner node of the decomposition tree \(\mathcal M\) represents a subgraph \(G[V']\) and has two child nodes. One of them corresponds to a module M of \(G[V']\), while the other represents a copy of \(G[V']\) with M contracted to a single vertex \(v_M\). Now we first consider the node of module M and solve KCG on G[M] recursively. This returns an array \(z_p(M)\) which we assign to the vertex \(v_M\) in the second child node as \(d_p(v_M)\). Note that by definition of a module it does not matter which items from M are included in a solution represented by \(z_p(M)\). Any solution in \(G[V' \setminus M]\) which is not in conflict with the new vertex \(v_M\) can also be combined with any solution for M.
Then we proceed recursively and let this second child node take over the role of the inner node, i.e. \(V' := V' \setminus M \cup \{v_M\}\). At the end of this recursive process we are left with a prime graph for which we can solve KCG by assumption.
Note that this prime graph is the unique leaf of the modular decomposition tree which is reached from the root by a path that never moves to a child node representing a module. Thus, the solution for this final leaf contains the information of all modules separated before and constitutes the solution of KCG on the original graph G.
3.2 Clique decomposition
Given a graph G, we follow the approach described by Tarjan (1985) for the maximal weight independent set problem and find a clique separator C which separates G into components A and B such that \(G[A\cup C]\) is an atom. In fact the decomposition procedure described by [Tarjan (1985), Sec. 2] separates an atom in each step and runs in O(nm) time. Analogous to the modular decomposition, we first consider the atom \(G[A \cup C]\). Later, \(G[B \cup C]\) will be considered recursively.
Each vertex \(q \in C\) might be selected in a solution. If this is the case, it can be complemented by the best possible solution in G[A], which is not in conflict with q, i.e. the best solution in \(G[A \setminus N(q)]\). The profit and weight information of the resulting solutions containing q is then inserted into \(d_p(q)\). To include also the case that no vertex of C is selected, we add an auxiliary empty vertex e into C with \(N(e)=C\), \(d_0(e)=0\) and \(d_p(e)=\infty \) for \(p>0\). Formally, we have for every \(q \in C\):This equation determines the best, i.e. lowest weight solution for every possible profit value p by combining q contributing profit \(p_1\) with a compatible subset of A with profit \(p_2\).
$$\begin{aligned} d_p(q) := \min _{p_1,p_2} \left\{ d_{p_1}(q) + z_{p_2}(A\setminus N(q)) \mid p_1+p_2=p\right\} \text{ for } p=0,\ldots ,P \end{aligned}$$
(10)
By assumption, KCG can be solved for any atom of G in pseudopolynomial time. To evaluate (10) we also have to solve KCG on \(G[A\setminus N(q)]\), i.e. on the subgraph of an atom arising from eliminating a single vertex and its neighborhood. It is easy to see that the pseudopolynomial algorithm applies also to these subgraphs: In most cases property \(\mathcal {Q}\) will also be valid for all subgraphs of an atom and we are done. But even if this is not the case one can easily enforce the inclusion of q by temporarily setting the weight of q to 0 and its profit to P. Then we run the algorithm on the full atom, but replace each target profit p by \(p+P\). Trivially, q will be included in the solution and it is complemented by the best solution of KCG on the desired subgraph with profit p.
After completion of (10) all potential contributions of items in A to an overall solution are represented by array \(d_p(q)\) for all \(q \in C\). Since C is a clique, these can contribute to the overall solution at most once.
Then we proceed recursively and search for a clique separating an atom from \(G[B \cup C]\). This atom is treated as above with dynamic programming entries computed for each vertex in the separating clique.
Continuing this process, we finally obtain a graph which is separated into two atoms both of which can be resolved and their contribution contracted in the final separator. It remains to pick the vertex from this separator that delivers the best solution value.
It would be interesting to combine modular and clique decomposition in an arbitrary order and thus generalize the above setting to prime atoms instead of atoms of prime graphs. Indeed, this would make the dynamic programming evaluation much more complicated and we followed several steps in this direction in the spirit of [Brandstädt and Hoàng (2007), Theorem 8]. Unfortunately, it was stated in the recent paper by Brandstädt and Giakoumakis (2015) that the approach implied by [Brandstädt and Hoàng (2007), Corollary 9] does not seem to work and only the iterative process of considering atoms of a prime graph can be pursued.
3.3 Applications
It is clear from the construction that the clique decomposition yields O(n) atoms for a graph with n vertices since each decomposition step for some clique C separates at least one vertex. To solve (10) in each such step a pseudopolynomial algorithm for atoms has to be executed \(|C|+1\) times (i.e. O(n)) and a scan through all profit values has to be performed |C| times taking O(nP) time. Furthermore, the decomposition tree \(\mathcal M\) of the modular decomposition has O(n) leaves each of which requiring the execution of a pseudopolynomial algorithm for prime graphs. Without caring about the details of the running time, it follows that any pseudopolynomial algorithm for the atoms of prime graphs gives rise to a pseudopolynomial algorithm for the original graph as stated in Theorem 8.
We will now describe a few graph classes for which Theorem 8 implies a pseudopolynomial time algorithm for KCG based on properties \(\mathcal {P}\) and \(\mathcal {Q}\). Clearly, there are many more graph classes around where our framework would apply but we restrict ourselves to some more recent examples.
A co-chair is a graph with five vertices \(a, \ldots , e\) and six edges (a, b), (a, c), (b, c), (b, d), (c, d), (d, e). [Brandstädt and Giakoumakis (2012), Sec.3] give some examples for relevant classes of (hole, co-chair)-free graphs. Note that some members of this family are perfect graphs while others are not. It was shown in Brandstädt and Giakoumakis (2015) that atoms of prime (hole, co-chair)-free graphs are nearly weakly chordal (\(\mathcal {Q}\)). Since the modular decomposition of (hole, co-chair)-free graphs trivially yields (hole, co-chair)-free prime graphs (\(\mathcal {P}\)), we get from Corollary 7:
Corollary 9
There is an FPTAS for KCG on (hole, co-chair)-free graphs.
Given a co-chair, a paraglider arises from adding the additional edge (a, e). [Brandstädt et al. (2012), Sec.1] discuss the relevance of (hole, paraglider)-free graphs which are perfect graphs and contain chordal graphs as a subclass. They present a decomposition result [Brandstädt et al. (2012), Theorem 1] which states that the atoms of (hole, paraglider)-free graphs belong to one of the following three graph families (in fact this property is necessary and sufficient for (hole, paraglider)-free graphs). Each of them allows a simple pseudopolynomial algorithm for KCG
A diamond is a \(K_4\) with one missing edge. The structure of (hole, diamond)-free graphs, which generalize chordal bipartite graphs, was described in Berry et al. (2015). They showed that an atom of a (hole, diamond)-free graph is either a clique, or a chordal bipartite graph, or a matched co-bipartite graph. These properties are very similar to the characterization of atoms of (hole, paraglider)-free graphs given above and KCG can be solved in the same way. Summarizing, we have:
(i)
Complete multipartite graphs allow a partitioning of the vertex set into k subsets such that two vertices are adjacent if and only if they belong to different subsets. Clearly, any solution of KCG can contain only vertices from exactly one subset. It suffices to solve a standard knapsack problem for each subset and select the best of the k resulting solutions.
(ii)
Join of a chordal bipartite graph and a clique, where the former is a bipartite, hole-free graph. Since chordal bipartite graphs are exactly those bipartite graphs, which are weakly chordal, the solution of KCG follows from Sect. 2 by choosing between the optimal solution on the chordal bipartite graph and the best vertex of the clique.
(iii)
Join of a matched co-bipartite graph and a clique, where the former consists of two disjoint cliques of size k and the edges between the cliques form a matching with k edges. Obviously, KCG can be solved on such a graph by taking each vertex of one clique as a candidate and combine it with the best vertex (taking the weight constraint into account) of the other clique excluding the matching partner of the candidate.
Corollary 10
There is an FPTAS for KCG on (hole, diamond)-free graphs and on (hole, paraglider)-free graphs.
More special graph classes defined by certain forbidden subgraphs were described in Brandstädt et al. (2010) [with the correction mentioned in Brandstädt and Giakoumakis (2015)]. For some of them it could be shown that atoms of prime graphs resulting from modular decomposition of the given graph are e.g. nearly chordal and thus an FPTAS for KCG exists.
4 KCG on H-minor free conflict graphs
In this section we consider KCG restricted to a H-minor free conflict graph. A a graph H is a minor of G if H can be obtained by successively applying the following three operations on G: deleting isolated vertices, deleting edges and contracting edges. Moreover a graph class is called H-minor free if the graph H is not a minor of any of the graphs of this class. The most well-known H-minor free graph class are planar graphs.
By the strong \(\mathcal{NP}\)-hardness of the independent set problem on cubic planar graphs we immediately get that there cannot exist an FPTAS for KCG on H-minor free graphs. Complementing this negative result we will now show that there exists a PTAS for KCG on planar graphs. We will indeed more generally show that a result of Demaine et al. (2005) extends to a class of problems that includes KCG on H-minor free graphs as a special case.
If a graph property \(\pi \) valid for a graph G also holds for all of its subgraphs, then \(\pi \) is called hereditary. Demaine et al. (2005) defined the maximum cardinality (profit) induced subgraph problem for a graph property \(\pi \) (\(MISP(\pi )\)) as a maximum cardinality (resp. profit) subset of vertices S of a graph G such that the hereditary property \(\pi \) holds for the subgraph induced by S. They defined \(EMISP(\pi )\) to be the problem of finding the maximum cardinality (profit) set of edges \(S'\) which induces a subgraph that fullfills the hereditary property \(\pi \).
Theorem 11
[Demaine et al. (2005), Theorem 3.7] For any hereditary graph property \(\pi \) that can be solved in polynomial time on graphs of bounded treewidth, for any graph H, and for any \(\varepsilon > 0\), there is a polynomial-time \((1 + \varepsilon )\)-approximation algorithm for \(MISP(\pi )\) and \(EMISP(\pi )\) on H-minor-free graphs.
An important decomposition result for H-minor free graphs is also shown in Demaine et al. (2005).
Theorem 12
[Demaine et al. (2005), Theorem 3.1] For a fixed graph H, there is a constant \(c_H\) such that, for any integer \(k\ge 2\) and for every H-minor-free graph G, the vertices of G can be partitioned into k sets such that any \(k-1\) of the sets induce a graph of treewidth at most \(c_H k\). Furthermore, such a partition can be found in polynomial time.
In the following we consider a generalization of KCG. Let c be a knapsack capacity. We say that a graph G with vertex (resp. edge) weights w(v) (resp. w(e)) fullfils c if \(\sum _{v\in V}w(v) \le c\) (resp. \(\sum _{e\in E}w(e) \le c\)). Let p(v) and (resp. p(e)) be the profit of vertex v (resp. edge e). With this we define the maximum profit induced subgraph problem for a graph property \(\pi \) and a capacity c (\(MPISP(\pi ,c)\)) as finding a maximum profit subset S of vertices of a graph G such that the subgraph induced by S fullfils \(\pi \) and c. Similarly, we define \(EPISP(\pi ,c)\) as the problem of looking for the maximum profit edge set \(S'\) of G that induces a subgraph fulfilling \(\pi \) and c.
Theorem 13
Let \(\pi \) be a hereditary graph property and c a knapsack constraint. Let H be a fixed graph. If the problem \(MPISP(\pi ,c)\) (resp. \(EPISP(\pi ,c)\)) can be approximated by an \((1+\varepsilon )\) polynomial time approximation algorithm on graphs of bounded treewidth (for all fixed \(\varepsilon >0\)) we get:
-
For any fixed \(\delta > 0\), there is a polynomial time \((1 + \delta )\)-approximation algorithm for \(MPISP(\pi ,c)\) and \(EPISP(\pi ,c)\) on H-minor-free graphs.
Proof
We first concentrate on \(MPISP(\pi ,c)\):
By Theorem 12 we get disjoint subsets \(V_1, \ldots , V_k\) such that any \(k-1\) of them induce a graph of bounded treewidth. For each \(i \in \{1,\ldots ,k\}\) we solve the \((1+\varepsilon )\)-approximation algorithm on the graph induced by \(\bigcup _{j\ne i} V_j\) and take the best over all these solutions with profit value \(z^a\) and corresponding solution set of vertices \(S^a\). Note that the exact value of k and \(\varepsilon \) will be determined later. Let \(z^*\) denote the optimal solution value of \(MPISP(\pi ,c)\) with corresponding solution set \(S^*\). By \(S^*(V_i)\) we denote \(\{v | v \in S^* \cap v \in V_i\}\). Choosingwe get by an averaging argument:Let \(z_{l}\) denote the optimal solution value of \(MPISP(\pi ,c)\) on the subgraph induced by \(\bigcup _{j\ne l} V_j\):Note that the set of vertices leading to a profit of \(z^* - \sum _{v \in S^*(V_l)}p(v)\) is feasible by \(\pi \) being hereditary. For an \((1 + \delta )\)-approximation algorithm for \(MPISP(\pi ,c)\) on H-minor free graphs we need \((1+\delta ) \cdot z^a \ge z^*\). But we already have:So let \(\delta \) be given. If we choosewhich is equivalent toand \(k > \frac{1}{\delta } + 1\) (in order to guarantee \(\varepsilon > 0\)), we get the desired result.
$$\begin{aligned} \ell := \arg \min _{i\in \{1,\ldots ,k\}} \left\{ \sum _{v \in S^*(V_i)}p(v) \right\} \end{aligned}$$
(11)
$$\begin{aligned} \sum _{v \in S^*(V_l)}p(v) \le \frac{1}{k} z^* \end{aligned}$$
$$\begin{aligned} (1+\varepsilon ) \cdot z^a \ge z_{l} \ge z^* - \sum _{v \in S^*(V_l)}p(v) \ge z^* - \frac{1}{k} z^* = \left( \frac{k-1}{k}\right) z^* \end{aligned}$$
$$\begin{aligned} \left( \frac{k}{k-1}\right) \cdot (1+\varepsilon ) \cdot z^a = \left( 1 + \frac{1}{k-1} + \frac{k}{k-1} \cdot \varepsilon \right) \cdot z^a \ge z^* \end{aligned}$$
$$\begin{aligned} \delta > \left( \frac{1}{k-1} + \frac{k}{k-1} \cdot \varepsilon \right) , \end{aligned}$$
$$\begin{aligned} \varepsilon \le \left( \delta \cdot \frac{k-1}{k} - \frac{1}{k} \right) \end{aligned}$$
To obtain a PTAS for \(EPISP(\pi ,c)\) we have to solve the \((1+\varepsilon )\) approximation algorithm on bounded treewidth graphs k times on the disjoint union of the subgraphs induced by \(V_i\) and its complement \(\overline{V}_i\). Note that by Theorem 12 the subgraphs induced by \(V_i\) and \(\overline{V}_i\) both have bounded treewidth and therefore also their disjoint union. \(S^*\) denotes the set of edges leading to an optimal solution value \(z^*\). Nowdenotes the index giving the minimal profit of the edges included in \(S^*\) between \(V_l\) and \(\overline{V}_l\). Now, one can proceed in analogy to \(MPISP(\pi ,c)\) and get the desired result for the edge-valued case. \(\square \)
$$\begin{aligned} \ell = \arg \min _{i\in \{1,\ldots ,k\}} \left\{ \sum _{(v \in V_i, \bar{v} \in \overline{V}_i) \wedge ((v,\bar{v}) \in S^*) } p((v,\bar{v})) \right\} \end{aligned}$$
Pferschy and Schauer (2009) showed an FPTAS for KCG on graphs of bounded treewidth which immediately implies the following result.
Corollary 14
There exist a PTAS for KCG on H-minor free graphs.
As a prominent example, it follows from the famous Robertson-Seymour Graph Minors Theorem [cf. Diestel (2012), Sec. 12] that graphs which can be embedded without crossing on a surface of constant genus are H-minor free. Naturally, this includes planar graphs.
Corollary 15
There exist a PTAS for KCG on planar graphs and - more general - on graphs of bounded genus.
5 The knapsack problem with forcing graph KFG
From a graph theoretic point of view, KFG is equivalent to finding a vertex cover in a graph such that its total weight is not necessarily minimal, but does not exceed the given threshold c. Among all such vertex covers we want to maximize the total profit.
In this section we will show that all FPTAS results we derived for KCG also hold for KFG. To do so we transform KFG into a minimization knapsack problem with conflict graphs (MKCG) such that the optimal solutions of both problems coincide. Our pseudopolynomial time algorithms for KCG can be easily transferred to MKCG. Then Theorem 1 implies FPTASs for MKCG and thus also for KFG since both belong to the class of subset selection problems.
Note that the transformation of KFG to MKCG is indeed required (at least for weakly chordal graphs) since the algorithm for KCG on graphs whose potential maximal cliques can be listed in polynomial time (see Sect. 2) cannot be easily extended to KFG, however it can be extented to solve MKCG.
Finally, we will state other approximability results for KFG in Sect. 5.3.
5.1 Transforming KFG into a minimization knapsack problem with conflict graphs
The minimization knapsack problem (MKP) is a variant of the standard knapsack problem where the sum of profits should be minimized but the total weight should be at least as large as the given bound c [cf. Kellerer et al. (2004), Sec. 13.3].
It is well known that if \(S\subseteq V\) is the minimum weight vertex cover of a vertex weighted graph \(G=(V,E)\), then the complement \(V\setminus S\) is a maximum weight independent set. In a similar way we will show that the optimal value of KFG with forcing graph G is equal to the optimal value of the minimization knapsack problem with conflict graphs (MKCG) with conflict graph G:
$$\begin{aligned} (MKCG)\quad&\min&\sum _{j=1}^{n}p_{j}x_{j}\end{aligned}$$
(12)
$$\begin{aligned}&\text{ s.t. }&\sum _{j=1}^{n}w_{j}x_{j}\ge \sum _{j=1}^n w_j -c\end{aligned}$$
(13)
$$\begin{aligned}&x_{i}+x_{j}\le 1 \quad \forall \, \ (i,j)\in E \end{aligned}$$
(14)
$$\begin{aligned}&x_{j}\in \{0,1\} \quad j=1,\ldots ,n. \end{aligned}$$
(15)
Theorem 16
The optimal solution values of KFG and MKCG coincide.
Proof
Let \(P=\sum _j p_j\) and \(W=\sum _j w_j\). Let z be the optimal solution value of KFG with solution set S. By definition of KFG, S is a vertex cover in G with profit z and a weight \(w \le c\). This implies that \(V\setminus S\) is a feasible independent set in G with profit \(P-z\) and weight \(W-w\). Clearly \(V\setminus S\) is feasible for MKCG and also optimal: Otherwise there exists a feasible solution set \(S'\) for MKCG with profit value \(z'\) and \(z' < (P-z)\). But then \(V\setminus S'\) is a vertex cover in G which is also feasible for KFG with solution value \(P-z' > P-(P-z)\) contradicting the optimality of z for KFG. The other direction follows analogously. \(\square \)
Hence, any exact algorithm solving MKCG is also an exact algorithm for KFG. Moreover, since the result of Theorem 1 works for both maximization and minimization problems, any pseudopolynomial algorithm for MKCG immediately implies an FPTAS also for KFG.
5.2 Graphs of bounded treewidth and chordal graphs
MKP with demand bound c can be solved in general by dynamic programming by reaching [cf. Kellerer et al. (2004)] where for each possible profit value the solution set with maximum weight is calculated. The optimal solution can then be found as the set with minimal profit value and weight exceeding c. The running time of this dynamic programming approach is O(nP). For chordal graphs and graphs of bounded treewidth this algorithm serves as a basis for more complicated dynamic programming schemes solving MKCG: the algorithms presented in Pferschy and Schauer (2009) solve KCG by applying dynamic programming on the clique tree of a chordal conflict graph and on the tree-decomposition of a conflict graph of bounded treewidth. All the main ideas used in these algorithms carry over directly to MKCG and by Theorem 16 also to KFG. Also the time and space complexities remain the same (Table 2). Note that for graphs of treewidth k a constant factor of \(2^{k+1}\) is hidden in the O-notation.
Table 2
Time and space complexities for KFG on special forcing graphs
KFG / MKCG
| Time | Space |
|---|---|---|
Bounded treewidth |
\(O(nP^2)\)
|
\(O( n + P \log (n))\)
|
Chordal |
\(O((n+m)P^2)\)
|
\(O(\min {\{m, n\log (n)\}} P+m)\)
|
Therefore, we conclude:
Theorem 17
There exists an FPTAS for KFG (resp. MKCG) on forcing (resp. conflict) graphs of bounded treewidth and on chordal forcing graphs. \(\square \)
A necessary condition for the application of Theorem 1 is the existence of a feasible solution for every instance of a subset selection problem (cf. Sect. 1.1). This might be seen as a catch for deriving an FPTAS since for KFG (and also MKCG) it is in general \(\mathcal{NP}\)-complete to decide the existence of a feasible solution.
However, on graphs of bounded treewidth and chordal graphs we can compute a minimum vertex cover in polynomial time [see e.g. Brandstädt et al. (1999)] and thus decide the feasibility of an instance in a preprocessing step. The same preprocessing step can be done for all graph classes whose potential maximal cliques can be listed in polynomial time by applying the algorithm presented in Fomin and Villanger (2010) with the extension by Lokshtanov et al. (2014) (recall Remark 2 in Sect. 2).
For KFG with weakly chordal forcing graphs we can proceed in a similar way and adapt the pseudopolynomial algorithm given in Sect. 2 for KCG to MKCG, which immediately leads to an FPTAS for KFG. However, the technical details are quite involved. In the same way, also all FPTASs for KCG stated in Sect. 3.3 carry over into FTPASs for KFG on the same graph classes.
5.3 KFG on planar and perfect graphs
Since the vertex cover problem is known to be \(\mathcal{NP}\)-hard also on planar graphs (even with degree at most 3), it remains \(\mathcal{NP}\)-complete to decide whether a given instance of KFG has a feasible solution and thus no polynomial time approximation algorithm can be given for KFG on planar graphs (under \(\mathcal{P}\)
\(\ne \)
\(\mathcal{NP}\)). This should be seen in contrast to KCG, where a PTAS was given for planar graphs in Corollary 14.
An important superclass of weakly chordal graphs are perfect graphs. By using the result of Milanič and Monnot (2008) concerning the exact weighted independent set problem (EWIS) we will show the following negative result for KFG with perfect graphs as forcing graphs. A completely analogous result for KCG was given in Pferschy and Schauer (2009).
Theorem 18
KFG is strongly \(\mathcal{NP}\)-hard with perfect graphs as forcing graphs.
Proof
It was shown in Milanič and Monnot (2008) that EWIS is strongly \(\mathcal{NP}\)-complete on perfect graphs (in fact even for bipartite graphs of degree at most 3). Let I be an instance of EWIS in a graph G with vertex weights \(w_j\), which asks if an independent set with total weight exactly w exists. But this is equivalent to the question whether there exists a vertex cover in G with weight \(W - w\). Now consider an instance of KFG on G with item profits and weights equal to \(w_j\) and \(c=W - w\). Then by solving this instance of KFG one can immediately answer the given instance of EWIS. \(\square \)
Acknowledgments
Open access funding provided by University of Graz. We would like to thank Martin Milanič for valuable discussions. This research was funded by the Austrian Science Fund (FWF): P23829.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.