The satisfactory partition problem
12 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

The satisfactory partition problem

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
12 Pages
English

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, ...

Subjects

Informations

Published by
Reads 1 020
Language English

Exrait

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 (k3) 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´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 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⌈ ⌉+1sd1 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 (k3) are requested.
2
Preliminaries
The following notation will be used in the rest of the paper. For a graphG= (V, E), a vertexvV, and a subsetYVwe 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 defined as follows. Satisfactory Partition Input:A graphG= (V, E). Question:Is there a nontrivial partition (V1, V2) ofVsuch that for everyvV, ifvVi 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) vV, ifvVithendVi(v)≥ ⌈2? d(v) ConsideringAV, a vertexvAis said to besatisfiedinAifdA(v)≥ ⌈ . Moreover 2 Ais asatisfactory subsetif all of its vertices are satisfied inA. IfA, BVare 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 vertexvViissatisfiedifdV(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. LetV1=A d(v) andV2=B. While there is a vertexvinV\(V1V2) such thatdV1(v)≥ ⌈ , insertvinto 2 d(v) V1there is a vertex. While vinV\(V1V2) such thatdV2(v)≥ ⌈ , insertvintoV2. At 2 d(v)d(v) the end, ifC=V\(V1V2)6=, thendV1(v)<⌈ ⌉anddV2(v)<⌈ ⌉for anyvC. For 2 2 d(v)d(v) anyvCwe havedVC(v)≥ ⌈ an )≥ ⌈ 12ddV2C(v2we 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 find a partition when it exists. In particular, all cubic graphs exceptK4andK3,3are partitionable and all 4regular graphs exceptK5are partitionable. We first 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 first 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 vertexviwithi6 has at most two neighbors among{v2, v4, v5}all vertices. If viwithi6 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. viwithi7 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 lengthk5, then no external vertex can have more than one neighbor inC, for otherwiseGwould contain a cycle of length at mostk/2+ 2< k, contradicting the choice ofC(. Thus, V1, V2) withV1=V(C) andV2=V\V1is a satisfactory partition.
Proposition 3Each 4regular graph exceptK5is partitionable.
Proof :LetGbe a 4regular 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, i5 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 k4, then there are no three vertices onCwith a common neighbor outsideC, since otherwise there exists inGa cycle of length at mostk/3For+ 2. k4 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 4regular 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 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 V1V(C) whilethere exists a vertexvV\V1with at leastd1 neighbors inV1do V1V1∪ {v} end while V2V\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 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 somes3, then up to distancesfrom the root ofTwe havedcomplete (d1)ary trees attached to the root; and if the cycle is also longer than 2s+ 1, then this ³ ´ P s1i subtree of heightsis aninducedsubgraph ofG. Thus,n > d(dand if1) holds, i=0 ³ ´ P s1i s the length exceeds 2sthen also+ 1, n > d(d1) + (d1) . 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 eachvV\V1, whose value is set to 0 at the beginning. We also define 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 valued1, 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 3d4, thewhileloop takes 2 justO(n) time.
Theorem 5All cubic graphs exceptK4andK3,3are partitionable in linear time.
Proof :LetGbe a cubic graph of ordern. The casesn10 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 mostvertices fromV\V1toV1moving. Indeed, mvertices yields|V1|=+m, and thisV1induces at least+ 2medges. Thus, the average degree in the subgraph induced mbyV1which impliesis not smaller than 3 + , msinceGConsequently, 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 4regular graphs exceptK5are 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 GC, therefore the degree sum in the induced subgraphGCis at least 4(n)2= 2(n) + 2(n2)>2(n). That is, the average degree inGCis at least two, and thereforeGCcontains 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 4regular graphs except K5are partitionable. Moreover, as stated in the introduction, all 2regular graphs (cycles) exceptK3These results cannot be extended for regular graphs with degreeare partitionable. greater than 4 since there are 5regular graphs, different fromK6andK5,5that are not partitionable, and there are 6regular graphs different fromK7that 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 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 nonadjacent 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 degree1 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