Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an undirected connected graph, our goal is to remove some edges to make the graph disconnected. The constraint is that each node of the graph can not lose more than $m$ edges incident to it. I want to find the minimum $m$ for which the goal is achievable. Is there any efficient algorithm to compute this minimum $m$ (and/or which edges to remove)? Or is it NP-complete?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

It appears to be NP-complete even when m=1: see The Complexity of the Matching-Cut Problem, Maurizio Patrignani and Maurizio Pizzonia, WG 2001, http://dx.doi.org/10.1007/3-540-45477-2_26

share|improve this answer
    
It's even NP-complete with m = 1 and restricted to planar graphs, see portal.acm.org/citation.cfm?id=1598870. This also gives some classes of graphs for which there is a polynomial-time algorithm, though I suspect the constants can be huge (bounded tree-width?!). –  Harrison Brown Dec 1 '09 at 6:03
add comment

According to wikipedia, if your only constraint is minimizing the number of edges removes, it's easy. Now whether those algorithms are approriate for solving your problem as stated exactly or approximately, thats another question entirely. I'd guess that it's certainly easy (in at least one of an exact or approximate sense) as long as the graphs have some nice sparseness or geometric structure such as being planar or k regular.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.