THE MAXIMUM INDUCED BIPARTITE SUBGRAPH PROBLEM WITH EDGE WEIGHTS∗
DENIS CORNAZ† AND A. RIDHA MAHJOUB‡
Abstract. Given a graphG= (V, E) with nonnegative weights on the edges, the maximum induced bipartite subgraph problem (MIBSP) is to find a maximum weight bipartite subgraph (W, E[W]) of G. HereE[W] is the edge set induced byW. An edge subset F ⊆E is called in- dependent if there is an induced bipartite subgraph ofGwhose edge set containsF. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets, that is, the depen- dent sets that are not contained in any other dependent set. Using this, we give an integer linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. Moreover, we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph, and can then be solved in polynomial time. This yields a polynomial-time separation algo- rithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem. We also discuss some polyhedral consequences.
Key words. induced bipartite subgraph, edge weight, minimal dependent set, separation algo- rithm, polytope
AMS subject classifications. 05C85, 90C27, 90C57 DOI.10.1137/060650015
1. Introduction. A graph is called bipartite if its node set can be partitioned into two nonempty sets V1 and V2 such that no two nodes in Vi are linked by an edge, for i= 1,2. LetG= (V, E) be a graph. A subgraph (W, F) ofGis said to be induced ifF is the set of edges having both endnodes inW. Givenw, a function that associates with each edge e ∈ E a nonnegative weight w(e), the maximum induced bipartite subgraph problem (MIBSP) is to find an induced bipartite subgraph with maximum weight.
An edge subset F ⊆ E is called independent if there is an induced bipartite subgraph of G with edge set B ⊆ E such that F ⊆ B. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets of a graph G = (V, E). Using this, we give a 0-1 linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. We also show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph and can then be solved in polynomial time. This yields a polynomial-time separation algorithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem.
To the best of our knowledge, MIBSP has not been considered before in the literature. However, the maximum bipartite subgraph problem has been extensively investigated. Here, given a graph G = (V, E) and weights on the edges of G, the
∗Received by the editors January 15, 2006; accepted for publication (in revised form) March 26, 2007; published electronically August 29, 2007.
http://www.siam.org/journals/sidma/21-3/65001.html
†Equipe Combinatoire, UFR 921, Universit´´ e Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France. Current address: Laboratoire LIMOS, CNRS UMR 6158, Universit´e Blaise Pascal, Clermont II, 63177 Aubi`ere Cedex, France ([email protected]).
‡Laboratoire LIMOS, CNRS UMR 6158, Universit´e Blaise Pascal, Clermont II, 63177 Aubi`ere Cedex, France ([email protected]).
662
problem is to find a bipartite subgraph (not necessarily induced) with maximum weight. In [3] Barahona, Gr¨otschel, and Mahjoub describe several classes of facet defining inequalities of the associated bipartite subgraph polytope. They also present some methods with which new facet defining inequalities of that polytope can be constructed from known ones.
A graph is said to be weaklybipartiteif the bipartite subgraph polytope coincides with the polytope given by the trivial inequalities and the so-called odd cycle inequal- ities. Gr¨otschel and Pulleyblank [18] showed that the bipartite subgraph problem can be solved in polynomial time in that class of graphs. Barahona showed that planar graphs [1] and graphs G that contain two nodes which cover all the odd-cycles of G[2] belong to that class of graphs. In [10] Fonlupt, Mahjoub, and Uhry generalize these results by showing that the graphs noncontractible toK5are weakly bipartite.
Recently Guenin [19] gave a characterization for that class of graphs.
The closely related MIBSP with node weights has also been studied. Here we suppose that the weights are associated with the nodes of the graph, and the problem is to determine an induced bipartite subgraph with maximum weight. This problem has applications to the via-minimization problem which arises in the design of integrated circuits and printed circuit boards [6], [11]. In [4] Barahona and Mahjoub study the polytope BP(G) associated with this problem. They exhibit some basic classes of facet defining inequalities for BP(G) and describe several lifting methods. In [5] they study a composition technique for BP(G) in the graphs which are decomposable by one- and two-node cutsets. Fouilhoux and Mahjoub [12] (see also Fouilhoux [11]) study the polytope BP(G). They describe new classes of facet defining inequalities and discuss separation procedures. Using this, they develop a branch-and-cut algorithm for the problem and present some computational results. In [13] Fouilhoux and Mahjoub consider the via-mimization problem and show that this can be reduced to the MIBSP with appropriate node weights. Further applications of the MIBSP with node weights to the via-minimization problem and DNA sequencing are also discussed in [11].
A related work has been done by Cornaz and Fonlupt [7] on the maximum biclique problem. (A biclique is the edge set of a complete bipartite (not necessarily induced) subgraph). Although the MIBSP and the maximum biclique problem are different, this paper gives rise to some structural relations between the minimal dependent sets associated to both problems.
The paper is organized as follows. In the following section we give some notation, definitions, and preliminary results. In section 3 we study the dependent sets and give a characterization for these sets. In section 4 we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum odd circuit problem and can then be solved in polynomial time. In section 5 we discuss some polyhedral consequences and give some concluding remarks.
2. Definitions, notation, and preliminary results.
2.1. Definitions and notation. Throughout the paper we consider only simple graphs and digraphs. We will denote a graph byG= (V, E), whereV is thenode set and E is theedge set. An edge with endnodes uand v will be denoted by uv. For W ⊆V, we let E[W] denote the set of edges having both nodes in W. The graph G[W] = (W, E[W]) is the subgraph of G induced by W. If F ⊆ E, we let V(F) denote the set of nodes incident to edges of F, and G(F) = (V(F), F). Note that G(F) =G[V(F)] holds if and only if G(F) is an induced subgraph ofG.
We denote a directed graph (or digraph) by D = (V, A), where V is the node set and Athe arc set of D. An arc with initial nodeuand terminal node v will be
denoted byuv. (Note thatuv=vufor digraphs.)
A path in G(resp.,D) is an alternate sequence of nodes and edges (resp., arcs) P = v1, e1, v2, . . . , vk, ek, vk+1 such that k ≥ 1, all the nodes vi are distinct, and ei=vivi+1∈E(resp.,ei=vivi+1∈A) fori= 1,2, . . . , k. The nodesv1andvk+1are theextremitiesofP, and we will say thatPlinksv1andvk+1(resp.,v1tovk+1). The integer kis called the lengthof P, and P is said to beeven (odd) ifk is even (odd).
Ifv1=vk+1,P is called acycle (resp.,circuit). An edge linking two nonconsecutive nodes of a path (cycle) P is called a chord of P. A chordless cycle is also called a hole. Given a pathP, we let E(P) (resp.,A(P)) andV(P) denote the sets of edges (resp., arcs) and nodes ofP, respectively.
Given a vector x ∈ RE and T ⊆ E, we let x(T) denote
e∈Tx(e). Bipartite graphs have the following property.
Remark 2.1. A graph is bipartite if and only if it does not contain an odd cycle.
2.2. Signed digraphs. Asigned digraph consists of a digraphD= (V, A) and a subset Σ⊆A of arcs calledsigned arcs. The arcs inA\Σ are said to beunsigned.
Given a signed digraph D = (V, A), a circuit is said to be odd if it contains an odd number of signed arcs. Note that if ω ∈ RA is a weight vector, then finding a minimum weight odd circuit in D reduces to finding a minimum weight odd circuit in an unsigned digraph. In fact, for this, it suffices to replace every unsigned arc uv∈A\Σ by a pathu, uw, w, wv, v, wherewis a new node, and associate to the new arcsuw, wv the weight ω(uv)2 . Moreover, finding a minimum weight odd circuit in a digraph reduces to a shortest path problem [17] (see also [16]). As the weights are nonnegative, it can then be solved in polynomial time, using, for instance, Dijkstra’s algorithm [9].
2.3. Independent sets. Given a graphG= (V, E), we letB(G) denote the set of the edge sets of the induced bipartite subgraphs ofG, i.e.,
B(G) ={B⊆E: G(B) =G[V(B)] andG(B) is bipartite}. Hence the MIBSP is equivalent to
maximize{ω(B) :B∈ B(G)}.
Given a graphG= (V, E), a node subsetW ⊆V is called astable set ifE[W] =∅. Thestable set problem in Gconsists in finding a stable set of maximum cardinality.
Note that the stable set problem can be reduced to the MIBSP. In fact, consider the graph ¯G= ( ¯V ,E) obtained from¯ G by adding a universal node (a node adjacent to all the other nodes of G) and associate with the edges of ¯E the weight ω(e) = 1 if e∈E¯\Eandω(e) = 0 if not. It is easy to see that an optimum solution of the MIBSP in ¯Gwith respect to weight vectorωcorresponds to a maximum cardinality stable set in G. This implies that the MIBSP is NP-hard. The maximum cardinality MIBSP is to find a set in B(G) with maximum cardinality. In what follows we shall show that the maximum cardinality MIBSP is also NP-hard, which implies that MIBSP is strongly NP-hard.
Proposition 2.2. The maximum cardinality MIBSP is NP-hard.
Proof. We show that the stable set problem in a graphG= (V, E) reduces to the maximum cardinality MIBSP. As the former problem is NP-hard [14], the latter is also NP-hard.
Let ˜G= ( ˜V ,E) be the graph obtained from˜ G = (V, E) by considering a copy G = (V, E) of G and adding all the possible edges between V and V, that is,
V˜ =V ∪V and ˜E=E∪E∪ {vv :v ∈V,v ∈V}. Note that for every stable set S⊆V ofGand its copyS⊆V ofG, ˜G[S∪S] is a complete bipartite graph. Thus for every maximum cardinality solutionB ∈ B( ˜G) and every stable set S ⊆V of G, we have that|B| ≥ |S|2. In particular|B| ≥ |S∗|2, whereS∗is a maximum stable set ofG.
Now letB∈ B( ˜G) be of maximum cardinality and ˜S⊆V˜ a maximum cardinality stable set of ˜G such that every nodev ∈S˜ is incident to an edge in B. Obviously, either ˜S⊆V or ˜S ⊆V. Thus |S˜| ≤ |S∗|. As|B| ≤ |S˜|2, it follows that|B| ≤ |S∗|2. Consequently,|B|=|S˜|2=|S∗|2.
Denote byI(G) the set of the independent sets ofG, i.e., I(G) ={I⊆E: ∃B ∈ B(G), I ⊆B}.
Obviously,B(G)⊆ I(G). However, in general we have thatB(G) is a strict subset of I(G). For instance, consider the graphGconsisting of a path of three edges (e1, e2, e3).
Clearly, the edge subset I={e1, e3} is independent. However,G(I)=G[V(I)], and henceI /∈ B(G). Also note that, since the weights are nonnegative,
max{ω(I) : I ∈ I(G)}= max{ω(B) : B∈ B(G)}.
Therefore the MIBSP is equivalent to finding a maximum weight independent set in G. Moreover, we have the following which is a direct consequence of Remark 2.1.
Lemma 2.3. Given an edge set I⊆E,I∈ I(G)if and only if G[V(I)] contains no odd cycle.
In what follows we will denote byC(G) the set of the minimal dependent sets of G, i.e.,
C(G) ={C⊆E: C∈ I(G) andC∈ I(G)∀C⊂C}. We have the following.
Lemma 2.4. Given an edge setC⊆E,C∈ C(G)if and only if (i) there exists at least one odd cycle inG[V(C)], and
(ii) for every odd cycle Qof G[V(C)]and every edge f ∈C, there exists a node vf ∈V(Q)such that f is the unique edge ofC incident to vf.
Proof.
Necessity.
(i) This follows from Lemma 2.3.
(ii) LetQbe an odd cycle ofG[V(C)] andfan edge ofC∈ C(G). If the statement does not hold, it is not hard to see thatV(Q)⊆V(C\ {f}). But this implies thatC\ {f}is dependent, contradicting the minimality ofC.
Sufficiency. By Lemmas 2.4(i) and 2.3, we have that C /∈ I(G). Now suppose thatCis not minimal. Then there exists an edgef =uv∈Csuch thatC=C\{f} ∈ I(G). By Lemma 2.3, this implies thatG[V(C)] contains an odd cycle, say Q, and henceV(Q)⊆V(C). Moreover, by Lemma 2.4(ii), it follows that one of the nodes off, say v, belongs toV(Q) and is not incident to any edge in C. But this implies thatv∈V(Q)\V(C), a contradiction.
Figure 1 shows a subgraph which is induced by the node set of a minimal de- pendent set. The dependent set is presented by bold lines. We can remark that the subgraph contains an odd cycle, and that for every edgef of the dependent set, there is a node of the cycle such thatf is the only edge incident to it.
in F in E \ F
Fig. 1. A subgraph induced by a minimal dependent set.
3. Minimal dependent sets. The characterization of the minimal dependent sets, given by Lemma 2.4, is not strong enough to obtain certain polyhedral results for the MIBSP which we will present in the next sections. In this section we give a stronger characterization of the minimal dependent sets. This will be given in Theorem 3.2. To this end, we first introduce some definitions.
LetF⊆EandQbe an odd cycle ofG. A nodev∈V(Q) is said to beunsaturated with respect toF andQifv is not incident to any edge ofF∩E(Q); otherwisevis said to besaturated.
Definition 3.1. Given an edge setF ⊆E, we say thatF induces an obstruction with respect to an odd cycleQ if Qis an odd cycle of G[V(F)] and if conditions (1) and (2)below are satisfied.
(1) Every edgef ∈F\E(Q)is of the formf =vwwherev∈V(Q),w∈V\V(Q), and there is no edge inF\ {f} adjacent tof.
(2) Every edge inF∩E(Q)is adjacent to at most one edge ofF.
Figure 2 shows an obstruction induced by an edge setF with respect to the odd cycle on seven edges. We can remark here thatF does not correspond to a minimal dependent set. The edgese, f induce a minimal dependent set.
Let F ⊆ E be an edge set. And suppose that F induces an obstruction with respect to an odd cycle
Q=v1, e1, v2, e2, . . . , vk, ek, vk+1
of G[V(F)], where vk+1 = v1. Let e ∈ E[V(F)]\(F∪E(Q)). Edge e is called a diagonal (with respect to F and Q) if there is i ∈ {1, . . . , k} such that e= vivi+3, the edges ei, ei+2 are in F, and the edges ei−1, ei+1, ei+3 are in E\F (the indices are taken modulo k). And edge e is called a forward (resp., backward)wing (with respect to F and Q) if there is i ∈ {1, . . . , k} and a node w ∈V \V(Q) such that e = wvi with ei, wvi+2 ∈ F (resp., wvi−2, ei−1 ∈ F), and ei−1, ei+1, ei+2 ∈ E\F (resp.,ei−3, ei−2, ei ∈E\F). An edge is called awing if it is either a forward or a backward wing.
e
f
in F in E \ F
Fig. 2.An obstruction induced byF.
vi−1 v
i v
i+1 v
i+2 v
i+3
Wing
w Two overlapping wings
vi v
i+2 v
i+3 v
v i+4
i−1 v
i+1
Diagonal in F
in E’
Fig. 3. Wings and diagonals.
We say that two wingswvi andwvj overlapifvivj∈F. Note that if two wings overlap, then necessarily one is forward and the other is backward (see Figure 3 for an illustration).
The following theorem gives a characterization of the set of minimal dependent sets ofG.
Theorem 3.2. LetG= (V, E)be a graph and F ⊆E an edge subset ofE. Then F is a minimal dependent set if and only if F induces an obstruction with respect to an odd cycleQsuch that
(i) every edge ofE[V(F)]\(F∪E(Q))is either a diagonal or a wing, and (ii) no wings overlap.
Proof.
Necessity. Suppose F ∈ C(G). Let W =V(F). By Lemma 2.3, G[W] contains
an odd cycle. Let
Q=v1, e1, v2, e2, . . . , vk, ek, vk+1,
with vk+1 = v1, be an odd cycle of G[W] such that |F ∩E(Q)| is maximum. Let F1 =F∩E(Q), F2 =F\F1, and E =E[W]\(F ∪E(Q)). Note that by Lemma 2.4(ii), no edge ofF1is adjacent to an edge ofF2.
For the rest of the proof, we will need to consider paths ofG[W] with extremities in V(Q) and internal nodes inW \V(Q). IfP is a path ofG[W] linking two nodes vi andvj ofV(Q) such that E(P)∩E(Q) =∅ and none of the internal nodes ofP belongs toV(Q), we letP1=vj, ej+1, . . . , ei−1, viandP2=vi, ei, . . . , ej−1, vj(where the indices are modulo k) denote the edge-disjoint paths of Q between vi and vj. Note thatQ=P1∪P2. We also denote by Q1=P∪P1 andQ2=P∪P2 the cycles obtained by adding P to Q. Note that Q1 and Q2 are of opposite parity. We will suppose, without loss of generality, thatQ1 is odd andQ2is even.
By Lemma 2.4(ii), for every edgef ∈F, there exists a nodevf ∈V(Q) such that f is the only edge ofF incident to vf. By a similar argument, there is also a node vf1 ∈V(Q1) such thatf is the only edge of F incident tovf1 (vf1 and vf may be the same). We have the following claims.
Claim 1. Let P be a path ofG[W] linking two nodes vi andvj of V(Q)whose internal nodes belong to W\V(Q). Let f2, f2 ∈F2 and e∈E. Then the following cases cannot occur:
(a) P =vi, f2, vj,
(b) P =vi, f2, w, f2, vj with w∈W \V(Q), or (c) P =vi, f2, w, e, w, f2, vj withw, w ∈W\V(Q).
Proof. Assume thatP is of type (a), (b) or (c). Notice that iff ∈F ∩E(P2), thenvf1=vi orvj. Also note thatviandvjare both incident to an edge ofF\E(P2).
Then it follows thatF∩E(P2) =∅. Since|F∩E(P)| ≥1,|F∩E(Q)|<|F∩E(Q1)|. But this contradicts the maximality of|F∩E(Q)|.
Claim 2. F induces an obstruction with respect to Q.
Proof. Letf =wvf ∈F\E(Q). (Recall thatvf is the node of V(Q) such that f is the only edge ofF incident to it.) Ifw∈V(Q), thenw, f, vf is a path ofG[W].
But this is impossible by Claim 1(a). So suppose thatw∈V(Q). If there is an edge f=wvf ∈F, thenP=vf, f, w, f, vf is a path ofG[W], contradicting Claim 1(b).
In consequence,f is adjacent to no edge inF, and thus condition (1) of Definition 3.1 is satisfied.
Now let f = uvf be an edge of F ∩E(Q). Since F satisfies condition (1) of Definition 3.1,f is adjacent to no edge in F2. Moreover, we have thatvf is incident to no edge in F. Hencef is adjacent to at most one edge of F∩E(Q). Therefore condition (2) of Definition 3.1 is satisfied.
Claim 3. Every edge of E is incident to a node ofQ.
Proof. Suppose that for an edge e = ww of E, we have {w, w} ∩V(Q) = ∅. Since w, w ∈W \V(Q), there exist two edgesf =wvf and f =wvf ofF. Note thatvf =vf. Hencevf, f, w, e, w, f, vf is a path ofG[W], which contradicts Claim 1(c).
Claim 4. Let e∈E,f ∈F, andvi, vj ∈V(Q).
(1) If P =vi, e, w, f, vj is a path ofG[W], then eis a forward wing.
(2) If P =vi, f, w, e, vj is a path ofG[W], then eis a backward wing.
Proof. We prove (1), the proof of (2) is similar. AsQ2 is even, the pathP2must contain an even number of edges, and hence|E(P2)| ≥2. Moreover, as by Claim 2F
induces an obstruction with respect toQ, f is the only edge ofF incident tovj (w).
In consequence,vjis unsaturated. Moreover,vj is the unique unsaturated node ofP2. Indeed, ifv was a further unsaturated node ofP2, then there must exist an edge, say f, of F2 incident to v. As by Claim 2 F induces an obstruction with respect to Q, vf1 ∈V \V(Q). (Recall thatvf1 is the node ofV(Q1) such thatf is the only edge of F incident to it.) Thusvf1 =w. But this is impossible sincef is (the only edge ofF) incident tow. In consequence,eiis the unique edge ofF inP2 and thus|E(P2)|= 2.
Thereforeei−1,ej−1,ej are not inF, and henceeis a forward wing.
Claim 5. Lete∈E. IfP =vi, e, vj is a path ofG[W] withvi, vj ∈V(Q), then eis a diagonal.
Proof. As|P| is odd andQ2 is even,P2 must be odd, and therefore|E(P2)| ≥3.
AlsoP2contains no unsaturated nodes. In fact, ifP2contains an unsaturated nodev, then there must existf ∈F incident tovsuch thatv1f ∈V(P1). But this contradicts Claim 1(a). In consequence, two consecutive edges of E(P2) cannot both be in E. From Lemma 2.4(ii), it then follows thatei andej−1are the only edges ofF inE(P2) and that |E(P2)| = 3. We also have thatei−1 and ej are not inF, j =i+ 3, and ei+1∈/F. Thuseis a diagonal.
Claim 6. No wings overlap.
Proof. Suppose that there are two wingse=wvi+1 and e =wvi that overlap.
Note thatw, w ∈W \V(Q),w=w, andei =vivi+1∈F. The path P with edge set E(P) = {wvi−1, e, ei, e, wvi+2} has three edges in F. And the path P of Q with edge set E(P) = {ei−1, ei, ei+1} has only one edge in F. Note that both P andP are odd. Hence the cycle ˜Qobtained fromQ by replacingP byP is odd.
AsV( ˜Q)⊆W and|E( ˜Q)∩F|>|E(Q)∩F|, we have a contradiction.
By Claim 2, F induces an obstruction with respect to Q. If e ∈ E, then by Claim 3, e belongs to a path P of the form either vi, e, w, f, vj or vi, f, w, e, vj or vi, e, vj with vi, vj ∈V(Q), f ∈F, and w∈W \V(Q). It then follows by Claims 4 and 5 thateis either a wing or a diagonal. Moreover, by Claim 6, no wings overlap.
Sufficiency. Suppose thatF induces an obstruction with respect to an odd cycle Q satisfying (i) and (ii). By Lemma 2.3, F is a dependent set. We will show that F =F\ {f} is an independent set for everyf ∈F. LetW=V(F) and let us set as beforeQ=v1, e1, v2, e2, . . . , vk, ek, vk+1 withv1 =vk+1. First remark that iff is an edge of E(Q), as F induces an obstruction with respect to Q, at most one edge ofF is adjacent tof. Thus Qcannot be a subgraph of G[W]. If f links a node not in V(Q) to an unsaturated node, sayv, ofV(Q), then v is not a node of G[W] and againQis not a subgraph ofG[W].
Now assume, by contradiction, thatF\{f}is not inI(G). By Lemma 2.3,G[W] contains an odd cycle, sayD. Suppose thatDcontains an edgee=vivi+3 which is a diagonal with respect toF and Q. Thusei, ei+2 ∈F andei−1, ei+1, ei+3 ∈F. Also, sinceF is an obstruction,ei andei+2are the only edges ofF incident toviandvi+3, respectively. In consequence,f can be neitherei norei+2. Now if we replace in D e by the pathvi, ei, vi+1, ei+1, vi+2, ei+2, vi+3, we get a new cycle inG[W] which does not containeand which is still odd. We can reiterate this procedure until we get an odd cycle inG[W], still denoted byD, without diagonals with respect toF andQ.
Suppose thatV(D) contains a nodew∈V(Q). As w∈V(F), there is an edge, sayg, belonging toF2∩E(D) incident tow. By condition (1) of Definition 3.1, this edge is the only edge of F incident to w. Consequently, there must exist an edge g∈E(W)\((F∪E(Q))∩E(D)) incident tow. By our hypothesis,gis then a wing with respect to Q. Suppose, without loss of generality, that g = wvi is a forward wing. Hence g = wvi+2 ∈ E(D). Also note that ei is the only edge of F incident
to vi, which implies that f =vivi+1. If we replace in D the path vi, g, w, g, vi+2 by vi, ei, vi+1, ei+1, vi+2, we get an odd cycle in G[W]. Moreover, this new cycle does not contain the wingg. So, if we reiterate this procedure, we get an odd cycleD in G[W] which contains neither a diagonal nor a wing with respect to F and Q and whose nodes are all inV(Q). But this implies thatDcontains only edges ofQ, which contradicts the fact thatQis not a subgraph ofG[W].
4. Finding a minimum dependent set. In this section we consider the prob- lem of finding a minimum dependent set in a graph with nonnegative weights. Using the characterization of the minimal dependent sets given in section 3, we will show that this problem reduces to the minimum odd circuit problem in a signed directed graph, and can then be solved in polynomial time. Some polyhedral and algorithmic consequences of this result will be discussed in the next section.
LetG= (V, E) be a graph and (c(e),e∈E) a nonnegative weight vector associ- ated with the edges ofE. In what follows we are going to construct fromGa signed digraphD= (U, A). For convenience we will use the following notation.
For every nodeuofG,c(u) will denote the minimum weight of an edge incident to u, andeu a minimum weight edge incident to u. That is, c(eu) =c(u). Given a minimal dependent setF ∈ C(G) ofG, we let
Q=v1, e1, v2, e2, . . . , vk, ek, vk+1
denote the odd cycle of the obstruction induced byF. (Such a cycle exists by Theo- rem 3.2.) And we suppose that the sequencee1, . . . , ekfollows the clockwise order. We say that a nodevi∈V(Q) isleft-saturated (resp.,right-saturated) ifei−1(resp.,ei) is inF; otherwisevi is said to beleft-unsaturated (resp.,right-unsaturated). Note that, since by Definition 3.1 E(Q)\F =∅, Q has at least one left-unsaturated node and one right-unsaturated node. If vi is unsaturated (i.e., left- and right-unsaturated), we denote by fi the unique edge in F incident tovi. A node v is said to be a left- node (resp.,right-node) if v is either left-saturated or left-unsaturated (resp., right- saturated or right-unsaturated).
Now we define the signed digraphD= (U, A) (see Figure 4 for an illustration).
signed arc unsigned arc
vRS
vRU vLU
vLS
uRU uRS uLS
uLU
c(uv) c(uv)
c(u) c(u)
Fig. 4.The subdigraph ofDcorresponding to an edgeuvofG.
• For every node u ∈ V, consider four nodes uLS, uRS, uLU, uRU which corre- spond to the four possible states of u: left-saturated, right-saturated, left- unsaturated, and right-unsaturated. And consider four unsigned arcs: uLSuRS, uLSuRU, uLUuRS with weight 0 anduLUuRU with weightd(uLUuRU) =c(u).
• For every edge uv∈E consider four signed arcs: uRUvLU, vRUuLU with weight d(uRUvLU) =d(vRUuLU) = 0 anduRSvLS, vRSuLSwith weightd(uRSvLS) =d(vRSuLS) = c(uv).
Observe that the tail of an unsigned arc is always a left-node and the head is always a right-node. Also note that any sequence of arcs inDalternates between signed and unsigned arcs. In consequence, any circuit ofD has an even number of arcs.
We let Σ denote the set of signed arcs andU =A\Σ the set of unsigned arcs.
So a circuitQDofD is odd if|A(QD)∩Σ| is odd.
LetQD be a minimum weight odd circuit ofD with respect to the weight vector d. LetF be a minimum weight dependent set ofGwith respect to the weight vector c. In what follows we are going to show that d(QD) =c(F). As a consequence, we can compute minimum dependent sets by calculating minimum weight odd circuits in an auxiliary graph.
First we show thatc(F)≤d(QD). LetF be the set of edges uv ofGsuch that either
(i) uRSvLS is an arc ofQD, (ii) vRSuLS is an arc ofQD, or
(iii) the edgeuvis the minimum weight edgeeuincident touanduLUuRUis an arc ofQD.
The way we defined the cost vector d yields c(F) ≤ d(QD). Let w1, . . . , wq be the sequence of nodes of QD (where the indices are modulo q). Then the sequence u1, . . . , uq of nodes ofG, obtained by taking the node ui ifwiis either uLSi ,uRSi ,uLUi , oruRUi (note thatq ≤q), induces a subgraphH ofGwhose edges correspond to the signed arcs ofQD. SinceQD is odd,H contains an odd cycleQ. SinceQ is a cycle of the graph G[V(F)], by Lemma 2.3,F is dependent. As F is chosen minimum, c(F)≤c(F) and therefore
c(F)≤d(QD).
Now we show thatc(F)≥d(QD). Sincecis nonnegative we can assume thatFis minimal. By Theorem 3.2,F induces an obstruction with respect to an odd cycleQ.
Let P1 = vi, ei, . . . , vj−1, ej−1, vj be a path of Q such that all the edges of P1
are in F and ei−1, ej ∈/ F. The node vi is left-unsaturated and right-saturated, the nodes vi+1, . . . , vj−1 are left- and right-saturated, and vj is left-saturated and right-unsaturated. In the digraph D, the path P1 corresponds to a path P1D with node set V(P1D) = {vLUi , viRS, vi+1LS , vi+1RS , . . . , vLSj−1, vjRS−1, vLSj , vjRU}. The arc set of P1D is A(P1D) ={ai, σi, . . . , aj−1, σj−1, aj}, where ai, . . . , aj ∈ U are unsigned arcs with weight 0 andσl is a signed arc with costd(σl) =c(el) forl=i, . . . , j−1. Thus
d(P1D) =d(ai) +d(σi) +· · ·+d(aj−1) +d(σj−1) +d(aj)
=c(ei) +· · ·+c(ej−1)
=c(P1).
Let P2 = vi, ei, . . . , vj−1, ej−1, vj be a path of Q such that no edge of P2 is in F. The node vi is right-unsaturated, the nodes vi+1, . . . , vj−1 are left- and right- unsaturated, and vj is left-unsaturated. In D, there is a path P2D with node set
V(P2D) = {viRU, vLUi+1, vRUi+1, . . . , vjLU−1, vRUj−1, vjLU}. The arc set of P2D is A(P2D) = {σi, ai+1, σi+1, . . . , aj−1, σj−1}, where al ∈ U is an unsigned arc with cost c(vl) for l = i+ 1, . . . , j−1 andσi, . . . , σj−1 are signed arcs with cost 0.
Thus
d(P2D) =d(σi) +d(ai+1) +d(σi+1) +· · ·+d(aj−1) +d(σj−1)
=c(vi+1) +· · ·+c(vj−1)
≤
l=i+1,...,j−1
c(fl).
(Recall thatflis the unique edge ofFincident tovl.) Observe now thatQdecomposes into paths of types P1 and P2. The associated paths of D of types P1D and P2D form a circuit RD of D whose weight d(RD) is less than or equal to c(F). Since
|Σ∩A(RD)| = |E(Q)|, RD is an odd circuit of D. Then d(QD) ≤ d(RD), and therefore
c(F)≥d(QD).
So we can state the following theorem.
Theorem 4.1. The minimum dependent set problem with nonnegative weights can be solved in polynomial time.
5. Polyhedral consequences and concluding remarks. Given a graphG= (V, E), let IBSP(G) be the convex hull of the incidence vectors of the edge sets of induced bipartite subgraphs ofG.
LetP(G) be the polyhedron given by
0≤x(e)≤1 ∀e∈E,
(1)
x(C)≤ |C| −1 ∀C∈ C(G).
(2)
Obviously, inequalities (1) and (2) are valid for IBSP(G). Constraints (1) are called thetrivial inequalities. Constraints (2) will be called thedependent set inequalities.
Moreover, we have that MIBSP is equivalent to the integer program max {wx : x∈ P(G), x integer}.
Theseparation problem for a class of inequalities is to decide whether a given vector
¯
x∈QE satisfies the inequalities and, if not, to find an inequality that is violated by ¯x.
Given a vector ˜x∈RE+, let ¯x∈RE+such that ¯x(e) = 1−x(e) for all˜ e∈E. Clearly, there is an inequality of type (2) violated by ˜xif and only if the minimum weight of a dependent set with respect to ¯xis less than 1. It thus follows by Theorem 4.1 that the separation problem associated with inequalities (2) is solvable in polynomial time.
From [15] we then have the following corollary.
Corollary 5.1. The problem
max {wx : x∈ P(G)} can be solved in polynomial time.
A natural question that may be posed is to characterize the graphs for which the polytopeP(G) is integral. As it will turn out, these graphs are precisely the bipartite graphs.
Proposition 5.2. P(G)is integral if and only ifGis bipartite.
Proof. IfG= (V, E) is bipartite, then P(G) is given by the trivial inequalities, and hence any extreme point ofP(G) is integer.
Now suppose thatG= (V, E) is not bipartite, and letQ=v1, e1, v2, e2, . . . , v2k+1, e2k+1, v2k+2, wherev2k+2 =v1, be an odd cycle of G. We can assume that Q is a hole. Consider the solution ¯x∈RE given by
¯ x(e) =
k
k+1 if e∈E(Q),
0 if not.
Let Ci ={ei, ei+2, . . . , ei+2k} fori = 1, . . . ,2k+ 1 (the indices are modulo 2k+ 1).
Note that|Ci|=k+ 1. By Theorem 3.2, the Ci’s are in C(G). We also have that ¯x satisfies the system
x(Ci) =|Ci| −1 fori= 1, . . . ,2k+ 1, x(e) = 0 ∀e∈E\E(Q).
Furthermore it is not hard to see that ¯xis the unique solution of that system. Hence
¯
xis an extreme point ofP(G).
In contrast with the classical bipartite subgraph problem, the linear relaxation of the MIBSP does not seem to be quite strong. As it has been shown by Guenin [19], for the former problem, the trivial and the cycle inequalities suffice to describe the bipar- tite subgraph polytope in a large class of graphs (the weakly bipartite graphs) which contains, for instance, planar graphs and bipartite graphs. However, for the MIBSP, as shown by Proposition 5.2, the graphs for which the trivial and the dependent set inequalities completely describe IBSP(G) are reduced to the bipartite graphs. We can also notice that any inequality that is valid for the bipartite subgraph polytope is also valid for the IBSP(G). These inequalities are not, however, so strong for the MIBSP. To see this, consider, for instance, a clique (W, T) onpnodes in a graph G.
The inequalityx(T)≤ p2p2is valid for the bipartite subgraph polytope onGand is facet defining [3], whereas, any solution for the MIBSP can take at most one edge fromT.
e f e f e f e f
(c) (d) (b)
(a)
Fig. 5.The minimal dependent sets of size 2.
These negative observations motivated us to investigating new valid inequalities for IBSP(G). By Theorem 3.2, {e, f} ∈ C(G) if and only if the subgraph induced by the endnodes of e, f is one of the four graphs of Figure 5. Let us consider from G an auxiliary graph A(G) whose nodes correspond to the edges of G and such that two nodese, f are linked by an edge if and only if {e, f} ∈ C(G). Remark that any independent set of G is a stable set of A(G). (Note that the converse is not true.) Hence the so-called clique and odd cycle inequalities of the stable set polytope of A(G) (see [20]) given by
x(K)≤1 for every cliqueK ofA(G), (3)
x(C)≤ |C| −1
2 for every odd cycleC ofA(G) (4)
are valid for IBSP(G). Notice that the edge set of a clique ofGcorresponds to a clique of A(G). (Note that the converse is not true.) As it will turn out, the separation problem for inequalities (3) is NP-hard. The separation problem for inequalities (4) can be solved in polynomial time (see, for instance, [17]).
Proposition 5.3. The separation problem for inequalities (3)is NP-hard.
Proof. We use a reduction from the maximum clique problem. LetG = (V, E) be a graph. Add a node u and the edges uv for each v ∈ V to obtain the graph G˜ = ( ˜V ,E). Let ˜˜ x∈RE˜ given by
˜ x(e) =
1/k ife∈E˜\E, 0 ife∈E.
Clearly, there is a cliqueK in A( ˜G) with ˜x(K)>1 if and only if there is a clique of sizek+ 1 inG.
LetG= (V, E) be a (nonbipartite) graph and letQ andCi be as defined in the proof of Proposition 5.2, i= 1, . . . ,2k+ 1. Observe that ebelongs tok+ 1 different Ci’s for eache∈E(Q). As theCi’s are dependent sets inG, the following inequalities are valid for IBSP(G):
x(Ci)≤k fori= 1, . . . ,2k+ 1.
By summing these inequalities, we obtain the inequality (k+ 1)x(E(Q))≤k(2k+ 1).
Therefore the inequalities
(5) x(E(Q))≤ |E(Q)| −2, for every odd cycleQofG,
are valid for IBSP(G). Inequalities (5) also arise naturally since any independent set ofGuses at most|V(Q)| −1 nodes (and thus at most|E(Q)| −2 edges) ofQ. Note that inequalities (5) are different from the inequalities induced by the odd cycles of A(G). (If, for instance,G= (V, E) is an odd cycle with edge set, sayE={e1, . . . , e5}, thenA(G) has no edge, while Gproduces the inequalityx(E)≤3 of type (5) which is facet defining.) Inequalities (5) will be calledcycle inequalities.
Proposition 5.4. The separation problem for inequalities (5) can be solved in polynomial time.
Proof. Let ¯xbe a vector associated with the edges of G. We may suppose that ¯x satisfies the trivial inequalities. Lety ∈RE such thaty(e) = 1−x(e) for all¯ e∈E.
An inequality (5) is violated by ¯xif and only if y(E(Q))<2. Thus the separation problem for inequalities (5) reduces to finding a minimum odd cycle inGwith respect to the weight vectory. Asy(e)≥0 for alle∈E, this can be done in polynomial time as shown in [18].
It would be interesting to determine when the dependent, cycle, and clique in- equalities are facet defining for the polytope IBSP(G).
The approach presented in this paper can be adapted to handle the maximum induced forest and the maximum induced acyclic subgraph problems (see [8]).
Acknowledgments. We would like to thank the anonymous referees for their constructive comments. We are grateful to Herv´e Kerivin for many comments that have improved the presentation.
REFERENCES
[1] F. Barahona,On the Complexity of Max Cut, Rapport de recherche 186, IMAG, Universit´e Joseph Fourier, Grenoble, France, 1980.
[2] F. Barahona,On some weakly bipartite graphs, Oper. Res. Lett., 2 (1983), pp. 107–111.
[3] F. Barahona, M. Gr¨otschel, and A. R. Mahjoub,Facets of the bipartite subgraph polytope, Math. Oper. Res., 10 (1985), pp. 340–358.
[4] F. Barahona and A. R. Mahjoub,Facets of the balanced (acyclic) induced subgraph polytope, Math. Programming, 45 (1989), pp. 21–33.
[5] F. Barahona and A. R. Mahjoub,Compositions of graphs and polyhedraI:Balanced induced subgraphs and acyclic subgraphs, SIAM J. Discrete Math., 7 (1994), pp. 344–358.
[6] H.-A. Choi, K. Nakajima, and C. S. Rim,Graph bipartization and via minimization, SIAM J. Discrete Math., 2 (1989), pp. 38–47.
[7] D. Cornaz and J. Fonlupt,Chromatic characterization of biclique covers, Discrete Math., 306 (2006), pp. 495–507.
[8] D. Cornaz, H. Kerivin, and A. R. Mahjoub, The Maximum Induced Forest and Acyclic Subgraph Problems, LIMOS, Universit´e Blaise Pascal, Clermont-Ferrand, France, in prepa- ration.
[9] E. W. Dijkstra,A note on two problems in connection with graphs, Numer. Math., 1 (1959), pp. 269–271.
[10] J. Fonlupt, A. R. Mahjoub, and J. P. Uhry,Composition in the bipartite subgraph polytope, Discrete Math., 105 (1992), pp. 71–91.
[11] P. Fouilhoux,Graphsk-partis et conception de circuits VLSI, Ph.D. dissertation, D. U. 1555, Universit´e Blaise Pascal, Clermont-Ferrand, France.
[12] P. Fouilhoux and A. R. Mahjoub,Polyhedral results for the bipartite induced subgraph prob- lem, Discrete Appl. Math., 154 (2006), pp. 2128–2149.
[13] P. Fouilhoux and A. R. Mahjoub,Bipartization of Graphs, VLSI Design and DNA Sequenc- ing, LIMOS, Universit´e Blaise Pascal, Clermont-Ferrand, France, preprint, 2005.
[14] M. R. M. Garey and D. S. Johnson,Computers and Intractibility. A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.
[15] M. Gr¨otschel, L. Lovasz, and A. Schrijver,The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.
[16] M. Gr¨otschel, L. Lovasz, and A. Schrijver,Polynomial algorithms for perfect graphs, Ann.
Discrete Math., 21 (1984), pp. 325–356.
[17] M. Gr¨otschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.
[18] M. Gr¨otschel and W. R. Pulleyblank,Weakly bipartite graphs and the max-cut problem, Oper. Res. Lett., (1981), pp. 23–27.
[19] B. Guenin,A characterization of weakly bipartite graphs, J. Combin. Theory Ser. B, (2001), pp. 112–168.
[20] M. Padberg,On the facial structure of set packing polyhedra, Math. Programming, 5 (1973), pp. 199–215.