Skip to main content
Computer Science

Return to Answer

Do it "properly", using the decision problem forms of each problem.
Source Link
j_random_hacker
j_random_hacker
  • 5.5k
  • 1
  • 16
  • 22

Constructing an instance of CO from an instanceDecision problem forms of VC and CO

Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $E$ is incident on at least one chosen vertex?" We will construct an instance $(A, k')$ of CO that represents the question: "Given the matrix $A$ with elements in $\{-1, 0, 1\}$, is it possible to permute the columns of $A$ such that a 1 appears before a -1 on at least $k'$ rows?" These two problems are stated in decision problem form, whereby the answer to each is either YES or NO: formally speaking, it is this form of a problem that is NP-complete (or not). Let It is not too difficult to see that the more natural optimisation problem form stated in the OP's question is roughly equivalent in terms of complexity: binary search on the threshold parameter can be used to solve the optimisation problem using a decision problem solver, while a single invocation of an optimisation problem solver, followed by a single comparison, is enough to solve the decision problem.

Constructing an instance of CO from an instance of VC

Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Finally, set the threshold $k'$ for the constructed CO instance: $(n+1)m + n - k$. In other words, we allow at most $k$ rows in which a -1 appears before a +1. Let's call this number of violating rows the "cost" of a CO solution.

The correspondence between a solution to the CO instance and a set of vertices in the original VC instance is: Every column to the left of the fence corresponds to a vertex that is in the set, and every column to the right of the fence corresponds to a vertex that is not.

Clearly a VC solution using at most $k$ vertices yields a solution to the constructed CO instance with cost at most $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to the CO instance with cost at most $k$ yieldscorresponds to a vertex cover with at most $k$ vertices.

ObserveSuppose to the contrary that in any optimalthere exists a solution to CO, every row in the top $(n+1)m$ rows has a +1 before aCO instance with cost at most -1. (Suppose this were not the case, i.e.,$k$ that leaves some row in the top $(n+1)m$ rows haswith a -1 before a +1: Then the same must hold for every. This row in thisbelongs to a block of $n+1$$(n+1)$ rows, since every column behaves the same way across each of these blocks corresponding to a particular edge $uv$. This Every row in this block ofin the original instance $A$ is identical by construction; permuting columns may change these rows corresponds to an uncovered edge, which can only occur if bothbut does not affect the columnsfact that correspond to the endpoints of this edge appear to the right of the fencethey are identical. Moving either Thus each of these columns from the right side of the fence to the left side would repair every row in this block, saving $n+1$ -1s while costing onlyidentical rows has a single -1, and thus improving before a +1 in the total score bysolution, implying a cost of at least $n$$n+1$. Thus the original solution could not have been optimal But $k \le n < n+1$: contradiction.)

Constructing an instance of CO from an instance of VC

Let the input VC instance be $(V, E)$. Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Clearly a VC solution using $k$ vertices yields a solution to the constructed CO instance with cost $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to CO with cost at most $k$ yields a vertex cover with at most $k$ vertices.

Observe that in any optimal solution to CO, every row in the top $(n+1)m$ rows has a +1 before a -1. (Suppose this were not the case, i.e., some row in the top $(n+1)m$ rows has a -1 before a +1: Then the same must hold for every row in this block of $n+1$ rows, since every column behaves the same way across each of these blocks. This block of rows corresponds to an uncovered edge, which can only occur if both the columns that correspond to the endpoints of this edge appear to the right of the fence. Moving either of these columns from the right side of the fence to the left side would repair every row in this block, saving $n+1$ -1s while costing only a single -1, and thus improving the total score by $n$. Thus the original solution could not have been optimal: contradiction.)

Decision problem forms of VC and CO

Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $E$ is incident on at least one chosen vertex?" We will construct an instance $(A, k')$ of CO that represents the question: "Given the matrix $A$ with elements in $\{-1, 0, 1\}$, is it possible to permute the columns of $A$ such that a 1 appears before a -1 on at least $k'$ rows?" These two problems are stated in decision problem form, whereby the answer to each is either YES or NO: formally speaking, it is this form of a problem that is NP-complete (or not). It is not too difficult to see that the more natural optimisation problem form stated in the OP's question is roughly equivalent in terms of complexity: binary search on the threshold parameter can be used to solve the optimisation problem using a decision problem solver, while a single invocation of an optimisation problem solver, followed by a single comparison, is enough to solve the decision problem.

Constructing an instance of CO from an instance of VC

Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Finally, set the threshold $k'$ for the constructed CO instance: $(n+1)m + n - k$. In other words, we allow at most $k$ rows in which a -1 appears before a +1. Let's call this number of violating rows the "cost" of a CO solution.

The correspondence between a solution to the CO instance and a set of vertices in the original VC instance is: Every column to the left of the fence corresponds to a vertex that is in the set, and every column to the right of the fence corresponds to a vertex that is not.

Clearly a VC solution using at most $k$ vertices yields a solution to the constructed CO instance with cost at most $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to the CO instance with cost at most $k$ corresponds to a vertex cover with at most $k$ vertices.

Suppose to the contrary that there exists a solution to the CO instance with cost at most $k$ that leaves some row in the top $(n+1)m$ rows with a -1 before a +1. This row belongs to a block of $(n+1)$ rows corresponding to a particular edge $uv$. Every row in this block in the original instance $A$ is identical by construction; permuting columns may change these rows, but does not affect the fact that they are identical. Thus each of these $n+1$ identical rows has a -1 before a +1 in the solution, implying a cost of at least $n+1$. But $k \le n < n+1$: contradiction.

Source Link
j_random_hacker
j_random_hacker
  • 5.5k
  • 1
  • 16
  • 22

This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it:

Constructing an instance of CO from an instance of VC

Let the input VC instance be $(V, E)$. Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

For each vertex $v_i$, create a column in which:

  • among the top $(n+1)m$ rows, the $j$-th block of $n+1$ rows all contain a +1 when edge $e_j$ is incident on $v_i$, and 0 otherwise, and
  • the bottom $n$ rows are all 0 except for the $i$-th, which is -1.

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Proof

Intuitively, the -1s in the top of the "fence" column force the selection of a subset of columns to be placed to its left that together contain +1s in all these positions -- corresponding to a subset of vertices that are incident on every edge. Each of these columns that appears to the left of the "fence" has a -1 on a distinct row somewhere in the bottom $n$ rows, incurring a cost of 1; the +1s in the bottom of the "fence" ensure that all columns placed to its right incur no such cost.

Clearly a VC solution using $k$ vertices yields a solution to the constructed CO instance with cost $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to CO with cost at most $k$ yields a vertex cover with at most $k$ vertices.

Observe that in any optimal solution to CO, every row in the top $(n+1)m$ rows has a +1 before a -1. (Suppose this were not the case, i.e., some row in the top $(n+1)m$ rows has a -1 before a +1: Then the same must hold for every row in this block of $n+1$ rows, since every column behaves the same way across each of these blocks. This block of rows corresponds to an uncovered edge, which can only occur if both the columns that correspond to the endpoints of this edge appear to the right of the fence. Moving either of these columns from the right side of the fence to the left side would repair every row in this block, saving $n+1$ -1s while costing only a single -1, and thus improving the total score by $n$. Thus the original solution could not have been optimal: contradiction.)

Since each of the $m$ blocks of rows in the top $(n+1)m$ rows have a +1 before a -1, each of the corresponding edges is covered by a vertex corresponding to a column to the left of the fence: that is, this subset of vertices constitutes a vertex cover. Since none of the top $(n+1)m$ rows have a -1 before a +1, the only place where cost can accrue in the solution is in the bottom $n$ rows, from columns placed to the left of the fence. Each such column has cost exactly 1, so given that the cost is at most $k$, there must be at most $k$ such columns, and hence at most $k$ vertices in the cover.

Finally, it's clear that the CO instance can be constructed in polynomial time from the VC instance, meaning that if a polynomial-time algorithm existed for solving CO, any VC instance could also be solved in polynomial time by first constructing a CO instance as described above and then solving it. Since VC is NP-hard, CO is too.