Grille couvrant par des rectangles

Question

Nous avons une grille $ N_1 Times N_2 $. Nous avons une collection de rectangles sur cette grille, chaque rectangle peut être représenté comme un $ n_1 $ -BY- $ n_2 $ matrice binaire $ r $. Nous voulons couvrir la grille de ces rectangles.

La version de décision de ce problème de couverture définit est-elle NP-complete?

• Entrée: collection $ mathcal {c} = {r_1, r_2, dots, r_l } $ de rectangles sur la grille (taille d'entrée: $ n_1n_2l $), et $ k in mathbb {n} ^ + $ $
• Sortie: sous-ensemble $ mathcal {s} sous-ensemble mathcal {c} $ avec $ | mathcal {s} | leq k $ et $ mathcal {s} $ contenant pour chaque cellule au moins un rectangle le couvrant.

J'ai constaté que le cas 1D ($ n_2 = 1 $) peut être résolu en temps polynomial par programmation dynamique: toute couverture optimale sera l'union de

• Une couverture optimale pour un sous-problème de couvrant les premières cellules $ N_1-N_1 $.
• Un rectangle 1D, c'est-à-dire un intervalle, couvrant les cellules $ n_1 $ restantes.

Je ne pense pas que DP puisse fonctionner pour le problème 2D: pour le problème 1D, vous avez un $ N_1 $ sous-problèmes à résoudre, mais pour 2d vous avez $ binom {n_1 + n_2} {n_2} $ sous-problèmes (nombre de nombre de Chemins de réseau nord-est sur la grille).

Je pense que le problème peut être NP, mais je ne suis pas sûr (bien qu'il semble plus difficile que P), et je n'ai pas réussi à trouver une réduction polynomiale d'un problème NP-Complete (3-SAT, couverture de sommet, ...)

Toute aide ou indice est la bienvenue.