(Guest post from Richard Taylor who requests information on a problem.)
The following graph partition problem arises in connection with studies
I am doing on a particular dynamical systems problem. I wonder if there
are any complexity results on it. Given a 3-regular graph, can the
vertex set be partitioned into 2 sets in such a way that the induced
subgraphs formed each have vertices of degree at least 2? Could this be
NP complete? There are a few results on vertex partitions I have found
in the literature - but none quite like this.
First Request from Bill G: In the past I have posted on problems and have
had comments tell me that its well known or falls out easily from
some theory, but then not give me a reference or proof sketch. Please, if
you are going to say its known, give a reference or proof sketch.
Doesn't it follow from Azuma that for large enough graphs this is true? Take a random partition of the graph into two sets A,B. The expected number of vertices in A (or B) with min-degree is Omega(n). On the other hand "exposing" the location of any fixed vertex, changes the number of vertices in A of min-degree 2 by at most 3. So with high probability both A and B will a linear number of vertices of min-degree 2. But I might have missed something...
ReplyDeleteDo you mean that **all** of the vertices of each subgraph have degree at least 2? Otherwise (**at least one** vertex of each subgraph has degree at least 2) it's always true for large enough n -- take a vertex u, put it and all its neighbours in one set S, everything else in the other. If n>1+3+9, there is a vertex at distance 3 from u, and it lives outside of S along with all its neighbours.
ReplyDeleteAssuming the other version: you are looking for a (not necessarily perfect) matching which is also a cut set? Sounds interesting.
This problem is called the "Satisfactory Problem". i.e. Given a graph, can we partition the vertices into two sets such that each vertex has at least as many neighbours in it's set as in the other set. C. Bazgan, Z.Tuza and D.Vanderpooten have a survey in the European Journal of Operations Research (2009) on this problem where they show that all cubic graphs without K_4 or K_{3,3} have such a partition. I don't know how you would compute such a partition though...
ReplyDeleteFor questions like this, try mathoverflow.net
ReplyDeleteI second commenter #2. How could anyone post a "request for info" on the most popular CS blog without making sure that his question is posed in a clear way?? This is maddening.
ReplyDeleteApologies for any ambiguity in the problem statement - but the response that identified it as the Satisfactory Problem has nailed the meaning I wanted. Many thanks.
ReplyDeleteRich T
cookies or crackers? what DO you feed the anonymous (#5) trolls who post here?
ReplyDeleteJudging from the demeanor and persistence of the complexity blog trolls, it must be a high-protein diet of some sort.
ReplyDelete@anon5: Please show some restrain. If you don't like it, does not mean you have to bully it. If the owner of this blog believe the problem statement is reasonable, he has his rights to publish it. In this particular case, what you suggest is trivial and cant be what someone is looking for.
ReplyDeleteactually anon #5= #4 if you *really* think and count properly. What's wrong with you guys ... can't you count ? Seriously ... ughh ...
ReplyDeleteHere's a reference to a similar problem:
ReplyDeleteNoga Alon and Nick Wormald, High degree graphs contain large-star factors.
Not sure about the d=3 case, though.