1
Thesatisfactorypartitionproblem
∗ Cristina Bazgan
† Zsolt Tuza
∗ Daniel Vanderpooten
Abstract TheSatisfactory Partitionproblem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [GK98, GK00] and further studied by other authors but its complexity re mained open until now. We prove in this paper thatSatisfactory Partition, as well as a variant where the parts are required to be of the same cardinality, areNPcomplete. However, for graphs with maximum degree at most 4 the problem is polynomially solv able. We also study generalizations and variants of this problem where a partition intok nonempty parts (k≥3) is requested.
Keywords:Satisfactory partition, graph, complexity, polynomial algorithm,NPcomplete.
Introduction
Gerber and Kobler introduced in [GK98, GK00] the problem of deciding if a given graph has a vertex partition into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. A graph satisfying this property is calledpartitionable. As remarked by Gerber and Kobler,Satisfactory PartitionInmay have no solution. particular, the following graphs are not partitionable: complete graphs, stars, and complete bipartite graphs with at least one of the two vertex sets having odd size. Some other graphs are easily partitionable: cycles of length at least 4, trees which are not stars, and disconnected graphs. After [GK98, GK00] this problem was further studied in [SD02], [GK03], [BTV03] and [GK04] but its complexity remained open until now, while some generalizations were studied and proved to beNPcomplete. Gerber and Kobler showed in [GK98, GK00] the strongNPhardness of a ﬁrst generaliza tion of this problem where vertices are weighted and we ask for a vertex partition into two nonempty parts such that for each vertex the sum of weights of the neighbors in the same part is at least as large as the sum of weights of the neighbors in the other part. Another generalization where theedgesare weighted was also proved to beNPhard in the strong sense. An “unweighted” generalization ofSatisfactory Partitionwas studied in [BTV03] where each vertexvis required to have at leasts(v) neighbors in its own part, for a given ∗ LAMSADE,Universite´ParisDauphine,PlaceduMarechaldeLattredeTassigny,75775ParisCedex16, France. Email:{bazgan,vdp}@lamsade.dauphine.fr † Computer and Automation Institute, Hungarian Academy of Sciences, Budapest; and Department of ComputerScience,UniversityofVeszpr´em,Hungary.Email:tuza@sztaki.hu .Research supported in part by the Hungarian Scientiﬁc Research Fund, grant T32969.
1
d functionsObviously, whenrepresenting the degree of satisﬁability. s=⌈ ⌉, wheredis 2 the degree function, we obtainSatisfactory Partitionproved in [Sti96] that if. Stiebitz d s⌉ −≤ ⌈ 1 then such a partition always exists; and we gave in [BTV03] a polynomialtime 2 d algorithm that ﬁnds one such partition. We also proved in [BTV03] that for⌈ ⌉+1≤s≤d−1 2 d the problem isNPcomplete. Only the complexity fors=⌈ ⌉remained open in [BTV03]. 2 We deﬁne in this paper another variant ofSatisfactory Partition, calledBalanced Satisfactory PartitionA, where the parts are required to have the same cardinality. graph admitting such a partition is said to bebalanced partitionable. One can easily see that graphs like cycles of even length and complete bipartite graphs with both vertex classes of even size are trivially balanced partitionable. A graph of even order formed by two non partitionable connected components of unequal size is an example of a graph partitionable but not balanced partitionable. We show in this paper thatSatisfactory Partitionand Balanced Satisfactory Partitionare polynomially equivalent andNPcomplete. The paper is structured as follows. Section 2 contains some notation, deﬁnitions of prob lems and a preliminary result. In Section 3, we prove that for graphs with maximum degree at most 4,Satisfactory Partitionis polynomially solvable and a satisfactory partition can be found in polynomial time if it exists. In Section 4 we show the polynomial equiv alence ofSatisfactory PartitionandBalanced Satisfactory Partition, and the NPIn Section 5 we study the complexity of some extensionscompleteness of these problems. where partitions intoknonempty parts (k≥3) are requested.
2
Preliminaries
The following notation will be used in the rest of the paper. For a graphG= (V, E), a vertexv∈V, and a subsetY⊆Vwe denote bydY(v) the number of vertices inYthat are adjacent tov; and, as usual, we writed(v) for the degreedV(v) ofvinV. The minimum and ′ maximum degree ofGwill be denoted byδ(G) and Δ(GFor any subgraph), respectively. G ′ ′ ′ ofG,V(G) andE(G) denote respectively the set of vertices and edges ofG. A partition (V1, V2) ofVis said to benontrivialif bothV1andV2are nonempty. The problems we are interested in are deﬁned as follows. Satisfactory Partition Input:A graphG= (V, E). Question:Is there a nontrivial partition (V1, V2) ofVsuch that for everyv∈V, ifv∈Vi d(v) ⌉? thendVi(v)≥ ⌈2 Balanced Satisfactory Partition Input:A graphG= (V, E) on an even number of vertices. Question:Is there a nontrivial partition (V1, V2) ofVsuch that|V1|=|V2|and for every d(v) v∈V, ifv∈VithendVi(v)≥ ⌈2⌉? d(v) ConsideringA⊆V, a vertexv∈Ais said to besatisﬁedinAifdA(v)⌉≥ ⌈ . Moreover 2 Ais asatisfactory subsetif all of its vertices are satisﬁed inA. IfA, B⊆Vare two disjoint, nonempty, satisfactory subsets, we say that (A, B) is asatisfactory pair. If, in addition, (A, B) is a partition ofV, then it will be called asatisfactory partitionand if the partition has the property|A|=|B|then it will be called abalanced satisfactory partitiona. Given d(v) partition(V1, V2) ofV, a vertexv∈ViissatisﬁedifdV(v)⌉≥ ⌈ . i 2
2
We establish now a necessary and suﬃcient condition to obtain a satisfactory partition that will be useful afterwards. In [GK00] and [SD02] some suﬃcient as well as necessary and suﬃcient conditions are also given for the existence of a satisfactory partition in a graph.
Proposition 1A graphG= (V, E)is partitionable if and only if it contains a satisfactory pair(A, B)if a satisfactory pair. Moreover, (A, B)is given, then a satisfactory partition of Gcan be determined in polynomial time.
Proof :The necessary part is obvious. The suﬃcient part is proved as follows. LetV1=A d(v) andV2=B. While there is a vertexvinV\(V1∪V2) such thatdV1(v)≥ ⌈ ⌉, insertvinto 2 d(v) V1there is a vertex. While vinV\(V1∪V2) such thatdV2(v)⌉≥ ⌈ , insertvintoV2. At 2 d(v)d(v) the end, ifC=V\(V1∪V2)6=∅, thendV1(v)<⌈ ⌉anddV2(v)<⌈ ⌉for anyv∈C. For 2 2 d(v)d(v) anyv∈Cwe havedV∪C(v)⌉≥ ⌈ an )≥ ⌈ 12ddV2∪C(v2⌉we can insert all vertices. Thus ofCeither intoV1or intoV2, forming a satisfactory partition.✷
3
Graphs with degrees bounded by 4
GraphsGwith Δ(G)≤4 are such that any subgraph induced by a cycle corresponds to a satisfactory subset. This property seems to make the problem easier, which is indeed the case since we can decide in polynomial time ifGwith Δ(G)≤4 is partitionable and ﬁnd a partition when it exists. In particular, all cubic graphs exceptK4andK3,3are partitionable and all 4regular graphs exceptK5are partitionable. We ﬁrst establish results on regular graphs.
Proposition 2Each cubic graph exceptK4andK3,3is partitionable.
Proof :LetGbe a cubic graph other thanK4andK3,3. IfGis disconnected it is trivially partitionable. Hence, we assume thatGis connected. Suppose ﬁrst thatGcontains a triangle and letCbe a triangle ofGwith verticesv1, v2, v3. Remark that a vertex outsideCcannot have all its neighbors onCsinceG6=K4. If each vertex ofV\V(C) has at most one neighbor onCthenV1=V(C) andV2=V\V1 form a satisfactory partition. Suppose that there is a vertexv4with two neighborsv1, v2onC. Ifv3andv4have a common neighborv5, thenV1={v1, v2, v3, v4, v5}andV2=V\V16=∅form a satisfactory partition ofG. OtherwiseV1={v1, v2, v3, v4}andV2=V\V16=∅form a satisfactory partition ofG. Suppose now thatGcontains a cycle of length 4 and does not contain a triangle. Let C=v1v2v3v4be a cycle of length 4. A vertex outsideCcannot have more than two neighbors onCsince otherwiseGwould contain a triangle. If each vertex ofV\V(C) has at most one neighbor onC, thenV1=V(C) andV2=V\V1 form a satisfactory partition. Otherwise, suppose that a vertexv5has neighborsv1andv3. SinceG6=K3,3there is no vertex ofGwith the three neighborsv2, v4, v5. Thus, a vertexviwithi≥6 has at most two neighbors among{v2, v4, v5}all vertices. If viwithi≥6 have at most one neighbor among {v2, v4, v5}thenV1={v1, v2, v3, v4, v5}andV2=V\V16=∅form a satisfactory partition of
3
Glet. Otherwise, v6be a vertex that hasv2, v4If all verticesas neighbors. viwithi≥7 have at most one neighbor among{v5, v6}, thenV1={v1, v2, v3, v4, v5, v6}andV2=V\V16=∅ form a satisfactory partition ofGthere is another vertex. Otherwise, v7with neighborsv5, v6. In this caseV1={v1, v2, v3, v4, v5, v6, v7}andV2=V\V16=∅form a satisfactory partition ofG. Finally, suppose thatGLethas no cycle of length at most 4. Cbe a shortest cycle inG. SinceChas lengthk≥5, then no external vertex can have more than one neighbor inC, for otherwiseGwould contain a cycle of length at most⌊k/2⌋+ 2< k, contradicting the choice ofC(. Thus, V1, V2) withV1=V(C) andV2=V\V1is a satisfactory partition.✷
Proposition 3Each 4regular graph exceptK5is partitionable.
Proof :LetGbe a 4regular graph other thanK5. IfGis disconnected it is trivially partitionable. Hence, we assume thatGis connected. Suppose thatGcontains a triangle and letCbe a triangle ofGwith verticesv1, v2, v3. If each vertex ofV\V(C) has at most two neighbors onC, thenGis partitionable, and V1=V(C) andV2=V\V1Otherwise letform a satisfactory partition. v4be a vertex with neighborsv1, v2, v3each vertex. If vi, i≥5 has at most two neighbors amongv1, v2, v3, v4then Gis partitionable withV1={v1, v2, v3, v4}andV2=V\V1since. Otherwise, G6=K5, there is a vertexv5with exactly three neighbors amongv1, v2, v3, v4. ThenV1={v1, v2, v3, v4, v5} andV2=V\V16=∅form a satisfactory partition ofG. Suppose now thatGis triangle free. LetCbe a shortest cycle inG. SinceChas length k≥4, then there are no three vertices onCwith a common neighbor outsideC, since otherwise there exists inGa cycle of length at most⌊k/3⌋For+ 2. k≥4 this would be a cycle shorter thanC(. Thus, V1, V2) withV1=V(C) andV2=V\V1is a satisfactory partition.✷
Clearly Proposition 2 and Proposition 3 show that a satisfactory partition for cubic graphs exceptK4andK3,3and 4regular graphs exceptK5We cancan be found in polynomial time. even show that, for these graphs, a satisfactory partition can be found in linear time using the following algorithm.
Algorithm 1Determination of a satisfactory partition for 3 and 4regular graphs,|V|>10 LetG= (V, E) be adregular graph (d= 3 or 4) of ordern >10. n Search a cycleCof length less than . 2 V1←V(C) whilethere exists a vertexv∈V\V1with at leastd−1 neighbors inV1do V1←V1∪ {v} end while V2←V\V1
RemarkThe conditionn >10 is purely technical; it is imposed to ensure that ford= 3 the input graph do have a cycle of length less thann/the other hand, for2. On d= 4, a cycle shorter thann/2 exists whenevern >8. What is more, in the 4regular case we would just need a cycle of length at mostn/2 (as shown later), and for this we should only assume n >5. The small cases, however, can be settled in constant time, therefore we have put a uniform bound onnthat works for bothd= 3 and 4.
4
It is immediately seen that, for bothd= 3 andd= 4, the algorithm terminates with a partition in which every vertex is satisﬁed, provided that the initial cycleChas been found. We will prove that the partition obtained is always nontrivial, and that the algorithm runs really fast. We begin with the latter, while the former will be split into two parts depending on the value ofd.
Lemma 4Algorithm 1 can be implemented to run in linear time.
Proof :We apply the BreadthFirst Search algorithm that ﬁnds a spanning treeTin the input graph in linear time. Ifeis the ﬁrst edge during BFS which does not become an edge of T, then thisetogether with a subpath ofTdeﬁnes a suﬃciently short cycle. (If this cycle is longer than 2s, for somes≥3, then up to distancesfrom the root ofTwe havedcomplete (d−1)ary trees attached to the root; and if the cycle is also longer than 2s+ 1, then this ³ ´ P s−1i subtree of heightsis aninducedsubgraph ofG. Thus,n > d(d−and if1) holds, i=0 ³ ´ P s−1i s the length exceeds 2sthen also+ 1, n > d(d−1) + (d−1) . From these bounds we i=0 obtainn >4s+ 4, as needed.) As regards thewhileloop, one solution for an eﬃcient implementation is to create a counter for eachv∈V\V1, whose value is set to 0 at the beginning. We also deﬁne a queue Qthat initially contains the vertices ofV1=V(Ceach step, we remove the head element). In wfromQand increase the counters of all neighbors ofwinV\V1; and if the counter of somevreaches the valued−1, we movevintoV1and put it at the end ofQ. The algorithm terminates whenQSince each edge is considered at mosthas become empty after some step. d two times during the procedure, and|E(G)|=|V| ≤2nfor 3≤d≤4, thewhileloop takes 2 justO(n) time.✷
Theorem 5All cubic graphs exceptK4andK3,3are partitionable in linear time.
Proof :LetGbe a cubic graph of ordern. The casesn≤10 can be handled in constant time. Forn >10, let us verify that Algorithm 1 withd= 3 (running in linear time) is correct. n We have seen thatℓ=|V(C)|<. The key observation now is that the algorithm can 2 move at mostℓvertices fromV\V1toV1moving. Indeed, mvertices yields|V1|=ℓ+m, and thisV1induces at leastℓ+ 2medges. Thus, the average degree in the subgraph induced m−ℓ byV1which impliesis not smaller than 3 + , m≤ℓsinceGConsequently, ifis cubic. m+ℓ n >10, Algorithm 1 stops with a satisfactory partition (V1, V2) where|V1| ≤2ℓ < n, which impliesV26=∅, i.e. the partition is nontrivial.✷
Theorem 6All 4regular graphs exceptK5are partitionable in linear time.
Proof :Assuming thatGis a 4regular graph of ordern >10, we are going to prove that Algorithm 1 withd= 4 is correct. n We have seen thatℓ=|V(C)|<. Each vertex ofChas at most two neighbors in 2 G−C, therefore the degree sum in the induced subgraphG−Cis at least 4(n−ℓ)−2ℓ= 2(n−ℓ) + 2(n−2ℓ)>2(n−ℓ). That is, the average degree inG−Cis at least two, and ′ thereforeG−Ccontains some cycleC. Clearly, Algorithm 1 stops before moving any vertex ′ ofCinto the setV1. Thus,V26=∅and the partition (V1, V2) obtained is satisfactory.✷
5
Thus, all cubic graphs exceptK4andK3,3are partitionable and all 4regular graphs except K5are partitionable. Moreover, as stated in the introduction, all 2regular graphs (cycles) exceptK3These results cannot be extended for regular graphs with degreeare partitionable. greater than 4 since there are 5regular graphs, diﬀerent fromK6andK5,5that are not partitionable, and there are 6regular graphs diﬀerent fromK7that are not partitionable (see Figure 1).
Figure 1: Nonpartitionable 5regular and 6regular graphs
We consider now graphs with maximum degree at most 4. In [GK04], it is indicated that such graphs with at least 13 vertices are always partitionable. We give necessary and suﬃcient conditions for the existence of satisfactory partitions, and show how to generate such a partition in polynomial time when it exists.
Proposition 7A graphGwithδ(G) = 3and contains two vertexdisjoint cycles.
Δ(G)≤4is partitionable if and only if it
Proof :(If) Immediate from Proposition 1. (Only if) IfGis partitionable then each vertex has at least two neighbors in its part, so each part contains a cycle.✷
Proposition 8LetGbe a graph withΔ(G)≤4Graphand with no isolated vertex. Gis partitionable if and only if there exists at most two disjoint edges that can be inserted between vertices of degrees 1 or 2, such that the resulting multigraph contains two vertexdisjoint cycles.
Proof :(If) IfGcontains two disjoint cyclesC1, C2thenV(C1) andV(C2) can be completed to form a satisfactory partition, using Proposition 1. IfGhas no two disjoint cycles but adding one edge (vi, vj), withd(vi), d(vj)≤2, the ′ graphG= (V, E∪ {(vi, vj)}) has two disjoint cyclesC1, C2then (vi, vj) belongs to one of these cycles. ThenV(C1) andV(C2) form a satisfactory pair once we remove (vi, vj) sincevi andvjhave degree at most two. Assume now that the addition of two nonadjacent edges (vi, vj),(vk, vℓ), withd(vi), d(vj), d(vk), d(vℓ)≤2, is such that the new graph contains two disjoint cycles. Since these two edges are not adjacent, as above, the two disjoint cycles can be completed to a satisfactory partition. (Only if) Let (V1, V2) be a satisfactory partition ofG. IfVi(i= 1,2) contains no cycle, then we add one edge between two degree1 vertices of a tree component insideVithe tree. If in question is just an edge, then we add a parallel edge creating a cycle of length 2 in the resulting multigraph.✷
6