Let $G'_{m,n}=(V,E)$ be the grid graph $G_{m,n}$, to which we add "diagonal" edges. For example, here is $G'_{6,3}$:


And for each vertex $v_i \in V$, we have a associated positive value $c_i$

Consider the following algorithmic task:

Input: $m,n,\{c_i\}_{v_i\in V}$ (in unary)

Output: The minimum weighted vertex cover of $G'_{m,n}$

Is this problem strongly NP-hard? I know the classical grid graph $G_{m,n}$ is a bipartite graph, so minimum vertex cover is equivalent to maximum matching (König's theorem) and thus is in P.

But here, $G'_{m,n}$ is not bipartite. I can't find a way to reduce this to a P problem, or to reduce a NP problem to this.

  • 1
    $\begingroup$ When you edit your question, please don't add "EDIT: Some more stuff" to the end. Instead, just edit your question to be what it should have been from the start. We have revision history to keep track of older versions, so there's no need to indicate what part was edited. $\endgroup$ – D.W. Oct 22 '15 at 21:59
  • $\begingroup$ I would expect that in the unweighted version, a p-time computable function depending only on $n$ and $m$ gives the answer due the regularity of the graph. $\endgroup$ – G. Bach Oct 23 '15 at 8:10
  • $\begingroup$ @D.W. : Understood. I changed the question as I am in fact more interested in the weighted version. If I understand "unary/binary" correctly, "unary" means I dont take into account encoding size of the data ? In that case, I suppose it's unary (which relates to strong NP-hardness, I believe ?). $\endgroup$ – Nihl Oct 23 '15 at 8:17
  • $\begingroup$ @G.Bach : Thanks for the insight. I am more interested in the weighted version. Because of the weights, there is no regularity of the graph. $\endgroup$ – Nihl Oct 23 '15 at 8:18
  • 1
    $\begingroup$ One optimal solution for the unweighted version should be: numbering rows top to bottom starting at $1$ and numbering columns left to right from $1$, in every odd row take every odd vertex, and in every even row, take all vertices. $\endgroup$ – G. Bach Oct 23 '15 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.