Given $S \in \mathbb{N}^{q\times n}$ for $q < n $ natural numbers, is there a pseudo-polynomial algorithm which can decide whether exists $x \in \{0,1\}^n$ such that $$ S \cdot x = \begin{bmatrix}t_1\\ ... \\ t_q \end{bmatrix} \in \mathbb{N}^q $$ ? Is it possible to modify for instance the dynamic programming for the subset sum problem?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
We can reduce 3-color to this problem with all elements being $0$ or $1$, so there is no pseudo-polynomial algorithm unless P = NP.
For each pair of (vertex, color) and (edge, color) we will have a column in $S$ (and position in $x$) such that colorings will correspond to $x$ having ones on positions corresponding to $(v_i, c_j)$ if $v_i$ is colored in $c_j$, and to $(e_i, c_j)$ if none of vertices incident to $e_i$ is colored in $c_j$.
Rows in $S$ (and elements in $t$) will correspond to vertices, edges and (color, edge) pair.
Column corresponding to $(v_i, c_j)$ has one in row corresponding to $v_i$, and also in all rows corresponding to $(e_k, c_j)$ for edges $e_k$ incident to $v_i$.
Column corresponding to $(e_i, c_j)$ has one in row corresponding to $e_i$ and one in row corresponding to $(e_i, c_j)$.
$t$ is just vector of all ones.
To get $1$ in $t$ in position corresponding to $v_i$, we need to have $1$ in exactly one positions of $x$ corresponding to $v_i$. So $x$ defines some coloring.
And the coloring is correct, because if we have two adjacent vertices colored in the same color, then position in $t$ corresponding to (edge between these vertices, color) will be $2$.
-
$\begingroup$ Thank you for answering! Will assuming $S \in \{0,1\}^{q \times n}$ help anyhow? In the sense that if a PTAS exists and the elements in the matrix $S$ are smaller than $\log(n)$, then can we take $\epsilon = \frac{1}{\log(n)}$ to obtain the exact solution and a complexity in $\mathcal{O}(n^{\log(n)})$ or so $\endgroup$C Marius– C Marius2024-05-17 18:29:39 +00:00Commented May 17, 2024 at 18:29
-
$\begingroup$ My reduction gives $S \in \{0, 1\}^{q \times n}$. I know next to nothing about approximations though. $\endgroup$mihaild– mihaild2024-05-18 01:46:39 +00:00Commented May 18, 2024 at 1:46