tag:blogger.com,1999:blog-3722233.post864389416924052667..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: A problem about Graph Partitions (guest post)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-55240448828384849972010-03-07T02:08:12.689-06:002010-03-07T02:08:12.689-06:00Here's a reference to a similar problem:
Noga ...Here's a reference to a similar problem:<br /><i>Noga Alon and Nick Wormald</i>, High degree graphs contain large-star factors.<br /><br />Not sure about the d=3 case, though.Unknownhttps://www.blogger.com/profile/04752384695446260553noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33429581685804970212010-02-19T20:49:09.858-06:002010-02-19T20:49:09.858-06:00actually anon #5= #4 if you *really* think and cou...actually anon #5= #4 if you *really* think and count properly. What's wrong with you guys ... can't you count ? Seriously ... ughh ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7710468295622294932010-02-19T13:57:10.756-06:002010-02-19T13:57:10.756-06:00@anon5: Please show some restrain. If you don'...@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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30730923093628943772010-02-19T09:41:17.733-06:002010-02-19T09:41:17.733-06:00Judging from the demeanor and persistence of the c...Judging from the demeanor and persistence of the complexity blog trolls, it must be a high-protein diet of some sort.Anonymoushttps://www.blogger.com/profile/11976987929795854783noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7330339585354277142010-02-18T19:14:26.786-06:002010-02-18T19:14:26.786-06:00cookies or crackers? what DO you feed the anonymo...cookies or crackers? what DO you feed the anonymous (#5) trolls who post here?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41195445634745008592010-02-18T16:53:02.356-06:002010-02-18T16:53:02.356-06:00Apologies for any ambiguity in the problem stateme...Apologies 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.<br /><br />Rich TRich Tnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64158280072362762452010-02-18T15:17:41.507-06:002010-02-18T15:17:41.507-06:00I second commenter #2. How could anyone post a &qu...I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22621350203323976012010-02-18T11:57:07.801-06:002010-02-18T11:57:07.801-06:00For questions like this, try mathoverflow.netFor questions like this, try mathoverflow.netJonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5292203962796089272010-02-18T10:00:04.348-06:002010-02-18T10:00:04.348-06:00This problem is called the "Satisfactory Prob...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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47157700851712555682010-02-18T09:57:37.784-06:002010-02-18T09:57:37.784-06:00Do you mean that **all** of the vertices of each s...Do 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.<br /><br />Assuming the other version: you are looking for a (not necessarily perfect) matching which is also a cut set? Sounds interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40674134161920691122010-02-18T09:40:09.966-06:002010-02-18T09:40:09.966-06:00Doesn't it follow from Azuma that for large en...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...Anonymousnoreply@blogger.com