Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Is it possible to determine if a problem set satisfies the "stable marriage" condition without finding the solution? (edit: added problem)

• I'm trying to determine if there is a way of determining wether or not a problem space is "convex" or not, which (as far as I can tell) is equivalent to asking how to determine the stable marriage condition. The problem with using a lineair algorithm to determine this condition is that it may very well find a local maximum, but this may not be indicative of the convex/non-convex nature of the problem space. Or, put in another way, is it possible to determine the linearity/non-linearity of a problem? (And is it determinable in linear time?) Edit: Here's the background on the actual problem, which is a specific version of the "matching" problem. Suppose you have about 200 students that alle wish to go abroad for one year and they get to choose where. They all have about 35 countries to choose from, with every country having only a specific amount of places available, ranging from 1 to 20. Every student is supposes to pick 3 to 5 choices, but not all of them do. About 60% make 3 choices, 15% make 2 choices, 15% have 4, 5% make only 1 choice and 5% enter alle possible 5 choices. The problem set is "congested", in essence there are enough places in total for all students, but some countries have a lot more demand that availability. Some students clearly have "bad lists", with all of their choices being heavily contested. The choices are not ranked, so students have no preference between choices. The best solution is the one that assigns the maximum amount of students one of their choices, the rank in which they enter there choices is not taken into account (every choice is equivalent). So, we're looking at maximum allocation. I have an ongoing discussion with a mathematician on wether or not this problem is NP or not and, more importantly, if it is a better idea to use a stochastic or a deterministic algorithm to find the best solution.  The mathematicians suggestion included looking at Hall's theorem and maximum flow approaches. Now, my contention is that for either approach to work, specific requirements would be needed. It would either have to have the "stable marriage condition" (for Hall's theorem) or be proven to be a linear problem (which I think is equivalent to the problem space being "convex") for maximum flow. My experimental impression is that this problem has many local maxima in which deterministic algorithms get "stuck". Conversely, the stochastic approach works very well and much better than Gale-Shapely for instance (about 90% placement with Gale-Shapely, 100% with a stochastic approach). However, it might be that there is a deterministic algorithm that works as well in P time. To know if that is the case, there are two approaches. One would be to try every deterministic algorithm out there (something I'm not too fond off) or somehow prove that the problem is not NP in the first place (which is my current assumption). Because of equivalency between Hall's theorem and about 4 others like it, any of the applicable theorems would probably be fine. A secondary confusion: if one can find a "perfect solution" (aka a transversal or SDR), would that imply via Hall's theorem that the problem satisfies the stable marriage condition?

• Answer:

  This is the maximum weight matching problem. It is solvable in polynomial time. Create a vertex for each student and a vertex for each open seat. Create an edge between a student and a seat if that student is interested in the seat and weight it appropriately by how interested the student is in the seat. For what you define as the "best solution" you can make all edge weights the same. Once you find a maximum matching assign each student to the seat they are matched with (if any). For more on the implementation of the algorithm you can start with http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm As for your second question, yes, a bipartite graph satisfies Hall's condition if and only if there exists a saturating matching. See http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem EDIT: In fact Edmond's matching algorithm is overkill for this problem since it deals with matchings in general graphs, not just bipartite graphs. You can get away with a simpler algorithm like the Hungarian algorithm. See http://en.wikipedia.org/wiki/Hungarian_algorithm