The satisfactory partition problem

Description

The satisfactory partition problem
∗ † ∗Cristina Bazgan Zsolt Tuza Daniel Vanderpooten
Abstract
The Satisfactory Partition problem 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 that Satisfactory Partition, as well
as a variant where the parts are required to be of the same cardinality, are NP-complete.
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 into k
nonempty parts (k ≥ 3) is requested.
Keywords: Satisfactorypartition,graph,complexity,polynomialalgorithm,NP-complete.
1 Introduction
GerberandKoblerintroducedin[GK98,GK00]theproblemofdecidingifagivengraphhasa
vertexpartitionintotwononemptypartssuchthateachvertexhasatleastasmanyneighbors
in its part as in the other part. A graph satisfying this property is called partitionable.
As remarked by Gerber and Kobler, Satisfactory Partition may have no solution. In
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
areeasilypartitionable: cyclesoflengthatleast4, ...

Sujets

• Partition héraldique
• Problème de couverture de sommets
• Neighbours
• Cycle
• Preuve de concept
• Comète de Encke

Informations

• Publié par: Shuim
• Nombre de lectures: 1 020
• Langue: English

Extrait

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, areNPcomplete. 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,NPcomplete.

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 beNPcomplete. Gerber and Kobler showed in [GK98, GK00] the strongNPhardness of a first 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 beNPhard 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´ParisDauphine,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:[e-mail] .Research supported in part by the Hungarian Scientific Research Fund, grant T32969.

1

d functionsObviously, whenrepresenting the degree of satisfiability. 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 polynomialtime 2 d algorithm that finds one such partition. We also proved in [BTV03] that for⌈ ⌉+1≤s≤d−1 2 d the problem isNPcomplete. Only the complexity fors=⌈ ⌉remained open in [BTV03]. 2 We define 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 andNPcomplete. The paper is structured as follows. Section 2 contains some notation, definitions 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 extensionscompleteness 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 byd Y (v) the number of vertices inYthat are adjacent tov; and, as usual, we writed(v) for the degreed V (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 (V 1 , V 2 ) ofVis said to benontrivialif bothV 1 andV 2 are nonempty. The problems we are interested in are defined as follows. Satisfactory Partition Input:A graphG= (V, E). Question:Is there a nontrivial partition (V 1 , V 2 ) ofVsuch that for everyv∈V, ifv∈V i d(v) ⌉? thend V i (v)≥ ⌈ 2 Balanced Satisfactory Partition Input:A graphG= (V, E) on an even number of vertices. Question:Is there a nontrivial partition (V 1 , V 2 ) ofVsuch that|V 1 |=|V 2 |and for every d(v) v∈V, ifv∈V i thend V i (v)≥ ⌈ 2 ⌉? d(v) ConsideringA⊆V, a vertexv∈Ais said to besatisfiedinAifd A (v)⌉≥ ⌈ . Moreover 2 Ais asatisfactory subsetif all of its vertices are satisfied 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(V 1 , V 2 ) ofV, a vertexv∈V i issatisfiedifd V (v)⌉≥ ⌈ . i 2

2

We establish now a necessary and sufficient condition to obtain a satisfactory partition that will be useful afterwards. In [GK00] and [SD02] some sufficient as well as necessary and sufficient 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 sufficient part is proved as follows. LetV 1 =A d(v) andV 2 =B. While there is a vertexvinV\(V 1 ∪V 2 ) such thatd V 1 (v)≥ ⌈ ⌉, insertvinto 2 d(v) V 1 there is a vertex. While vinV\(V 1 ∪V 2 ) such thatd V 2 (v)⌉≥ ⌈ , insertvintoV 2 . At 2 d(v)d(v) the end, ifC=V\(V 1 ∪V 2 )6=∅, thend V 1 (v)<⌈ ⌉andd V 2 (v)<⌈ ⌉for anyv∈C. For 2 2 d(v)d(v) anyv∈Cwe haved V∪C (v)⌉≥ ⌈ an )≥ ⌈ 1 2 dd V 2 ∪C (v 2 ⌉we can insert all vertices. Thus ofCeither intoV 1 or intoV 2 , 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 find a partition when it exists. In particular, all cubic graphs exceptK 4 andK 3,3 are partitionable and all 4regular graphs exceptK 5 are partitionable. We first establish results on regular graphs.

Proposition 2Each cubic graph exceptK 4 andK 3,3 is partitionable.

Proof :LetGbe a cubic graph other thanK 4 andK 3,3 . IfGis disconnected it is trivially partitionable. Hence, we assume thatGis connected. Suppose first thatGcontains a triangle and letCbe a triangle ofGwith verticesv 1 , v 2 , v 3 . Remark that a vertex outsideCcannot have all its neighbors onCsinceG6=K 4 . If each vertex ofV\V(C) has at most one neighbor onCthenV 1 =V(C) andV 2 =V\V 1 form a satisfactory partition. Suppose that there is a vertexv 4 with two neighborsv 1 , v 2 onC. Ifv 3 andv 4 have a common neighborv 5 , thenV 1 ={v 1 , v 2 , v 3 , v 4 , v 5 }andV 2 =V\V 1 6=∅form a satisfactory partition ofG. OtherwiseV 1 ={v 1 , v 2 , v 3 , v 4 }andV 2 =V\V 1 6=∅form a satisfactory partition ofG. Suppose now thatGcontains a cycle of length 4 and does not contain a triangle. Let C=v 1 v 2 v 3 v 4 be 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, thenV 1 =V(C) andV 2 =V\V 1 form a satisfactory partition. Otherwise, suppose that a vertexv 5 has neighborsv 1 andv 3 . SinceG6=K 3,3 there is no vertex ofGwith the three neighborsv 2 , v 4 , v 5 . Thus, a vertexv i withi≥6 has at most two neighbors among{v 2 , v 4 , v 5 }all vertices. If v i withi≥6 have at most one neighbor among {v 2 , v 4 , v 5 }thenV 1 ={v 1 , v 2 , v 3 , v 4 , v 5 }andV 2 =V\V 1 6=∅form a satisfactory partition of

3

Glet. Otherwise, v 6 be a vertex that hasv 2 , v 4 If all verticesas neighbors. v i withi≥7 have at most one neighbor among{v 5 , v 6 }, thenV 1 ={v 1 , v 2 , v 3 , v 4 , v 5 , v 6 }andV 2 =V\V 1 6=∅ form a satisfactory partition ofGthere is another vertex. Otherwise, v 7 with neighborsv 5 , v 6 . In this caseV 1 ={v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 }andV 2 =V\V 1 6=∅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, V 1 , V 2 ) withV 1 =V(C) andV 2 =V\V 1 is a satisfactory partition.✷

Proposition 3Each 4regular graph exceptK 5 is partitionable.

Proof :LetGbe a 4regular graph other thanK 5 . IfGis disconnected it is trivially partitionable. Hence, we assume thatGis connected. Suppose thatGcontains a triangle and letCbe a triangle ofGwith verticesv 1 , v 2 , v 3 . If each vertex ofV\V(C) has at most two neighbors onC, thenGis partitionable, and V 1 =V(C) andV 2 =V\V 1 Otherwise letform a satisfactory partition. v 4 be a vertex with neighborsv 1 , v 2 , v 3 each vertex. If v i , i≥5 has at most two neighbors amongv 1 , v 2 , v 3 , v 4 then Gis partitionable withV 1 ={v 1 , v 2 , v 3 , v 4 }andV 2 =V\V 1 since. Otherwise, G6=K 5 , there is a vertexv 5 with exactly three neighbors amongv 1 , v 2 , v 3 , v 4 . ThenV 1 ={v 1 , v 2 , v 3 , v 4 , v 5 } andV 2 =V\V 1 6=∅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, V 1 , V 2 ) withV 1 =V(C) andV 2 =V\V 1 is a satisfactory partition.✷

Clearly Proposition 2 and Proposition 3 show that a satisfactory partition for cubic graphs exceptK 4 andK 3,3 and 4regular graphs exceptK 5 We 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 4regular graphs,|V|>10 LetG= (V, E) be adregular graph (d= 3 or 4) of ordern >10. n Search a cycleCof length less than . 2 V 1 ←V(C) whilethere exists a vertexv∈V\V 1 with at leastd−1 neighbors inV 1 do V 1 ←V 1 ∪ {v} end while V 2 ←V\V 1

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 4regular 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 satisfied, 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 BreadthFirst Search algorithm that finds a spanning treeTin the input graph in linear time. Ifeis the first edge during BFS which does not become an edge of T, then thisetogether with a subpath ofTdefines a sufficiently 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−1 i subtree of heightsis aninducedsubgraph ofG. Thus,n > d(d−and if1) holds, i=0 ³ ´ P s−1 i 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 efficient implementation is to create a counter for eachv∈V\V 1 , whose value is set to 0 at the beginning. We also define a queue Qthat initially contains the vertices ofV 1 =V(Ceach step, we remove the head element). In wfromQand increase the counters of all neighbors ofwinV\V 1 ; and if the counter of somevreaches the valued−1, we movevintoV 1 and 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 exceptK 4 andK 3,3 are 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\V 1 toV 1 moving. Indeed, mvertices yields|V 1 |=ℓ+m, and thisV 1 induces at leastℓ+ 2medges. Thus, the average degree in the subgraph induced m−ℓ byV 1 which impliesis not smaller than 3 + , m≤ℓsinceGConsequently, ifis cubic. m+ℓ n >10, Algorithm 1 stops with a satisfactory partition (V 1 , V 2 ) where|V 1 | ≤2ℓ < n, which impliesV 2 6=∅, i.e. the partition is nontrivial.✷

Theorem 6All 4regular graphs exceptK 5 are partitionable in linear time.

Proof :Assuming thatGis a 4regular 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 setV 1 . Thus,V 2 6=∅and the partition (V 1 , V 2 ) obtained is satisfactory.✷

5

Thus, all cubic graphs exceptK 4 andK 3,3 are partitionable and all 4regular graphs except K 5 are partitionable. Moreover, as stated in the introduction, all 2regular graphs (cycles) exceptK 3 These results cannot be extended for regular graphs with degreeare partitionable. greater than 4 since there are 5regular graphs, different fromK 6 andK 5,5 that are not partitionable, and there are 6regular graphs different fromK 7 that are not partitionable (see Figure 1).

Figure 1: Nonpartitionable 5regular and 6regular 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 sufficient 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 vertexdisjoint 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 vertexdisjoint cycles.

Proof :(If) IfGcontains two disjoint cyclesC 1 , C 2 thenV(C 1 ) andV(C 2 ) can be completed to form a satisfactory partition, using Proposition 1. IfGhas no two disjoint cycles but adding one edge (v i , v j ), withd(v i ), d(v j )≤2, the ′ graphG= (V, E∪ {(v i , v j )}) has two disjoint cyclesC 1 , C 2 then (v i , v j ) belongs to one of these cycles. ThenV(C 1 ) andV(C 2 ) form a satisfactory pair once we remove (v i , v j ) sincev i andv j have degree at most two. Assume now that the addition of two nonadjacent edges (v i , v j ),(v k , v ℓ ), withd(v i ), d(v j ), d(v k ), 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 (V 1 , V 2 ) be a satisfactory partition ofG. IfV i (i= 1,2) contains no cycle, then we add one edge between two degree1 vertices of a tree component insideV i the 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