Your problem devolves to finding a maximal independent set in a graph of bounded degree (bounded by the number of forbidden distances). If you Google "independent set bounded degree" you will find various discouraging references. Of course your graphs aren't general bounded-degree graphs, but I doubt there is much leverage in the specific form of your graphs.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of James Propp Sent: Friday, February 26, 2016 11:10 PM To: math-fun Subject: [math-fun] Packing complexity question
Responses to my MO post http://mathoverflow.net/questions/232165/one-dimensional-packing-of- monomers-with-forbidden-distances haven't taught me anything.
Do any of you know (or can any of you figure out) how difficult packing problems of this kind are, from a complexity standpoint?
If S is held fixed, then F(n,S) is polynomial time, but that's not very interesting; I want to know what happens as S varies.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun