Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
2
votes
1answer
30 views
Reduction from 3-SAT to MAX 2SAT
For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an ...
0
votes
1answer
26 views
Is the generalized assignment problem with un-capacitated agents NP-hard?
I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed ...
1
vote
0answers
24 views
Filling a big rectangle with small rectangles
There are N numbers; their values are A1, A2, ..., An respectively, their sum is S. There is a big rectangle which area is S. You need to draw N number small rectangle which area is its value.
...
0
votes
0answers
12 views
How to solve $PARTITION$ using this optimization problem?
$PARTITON=\{<S>:\:S\:is\:a\:finite\:set\:of\:whole\:numbers\:and\:\exists T\subseteq S \:such \:that \sum T=\sum (S-T)\} \:$
The summation for $T$ for example is to sum all the numbers in $T$
...
0
votes
0answers
110 views
How can I prove that clust-p is NP-complete?
CLUST-P:
Instance: A a non-empty set, α : A × A → N, p, s ∈ N
Question: Does A have a partition, A1, A2, . . . , Ap, such that max α(u,v) <=s, u,v∈Ai ∀1 <= i <= p?
It is obvious that A ...
4
votes
2answers
61 views
Minimum transactions to settle debts among friends
You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
0
votes
0answers
44 views
Number of divisors of a number - in NP?
I'm trying to show that the language $\{(m,n) | m \space \text{has exactly} \space n \space \text{divisors}\}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the ...
0
votes
1answer
17 views
satisfying boolean n variable DNF formula
I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable.
the number of tuples in Z is not fixed, obviously <= ...
1
vote
0answers
11 views
Reduction of Steiner Tree to Maximum Weight Connected Subgraph
I want to proof that the MWCS is an NP-hard problem by proofing that its decision version is NP-Complete. Below I have my proof so far and I hope people can give comments whether it can be formulated ...
0
votes
0answers
25 views
Set cover problem NP completeness
I have a quick question about Set cover problem. In Wikipedia, < https://en.wikipedia.org/wiki/Set_cover_problem >, they are saying "The decision version of set covering is NP-complete, and the ...
0
votes
1answer
41 views
Show that the 3-color problem is in P when the input graph is a tree.
This one is from university assignment. I am completely stuck on this one and I searched the internet but couldn't find a explanation.
Show that the 3-color problem is in P when the input graph is ...
0
votes
0answers
18 views
Partition Problem Variant
I'd like to ask to solve a variant of set partition problem. Suppose we have some items $V = \{1, \cdots, n\}$ and a subadditive cost function $f: 2^V \to R^{+}$. For any partition $P$ of $V$, define ...
0
votes
0answers
10 views
Complexity of maximizing sum of fractional functions under cardinality constraint
Considering the following optimization problem:
$max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
1
vote
1answer
64 views
Maximizing the total number of feasible constraints of a linear program
I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger ...
0
votes
1answer
34 views
Positioning items to maximize separation subject to constraints
Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
41 views
Is the Maximum Clique Problem for Directed Acyclic Graphs NP complete as well?
Imagine I have a graph $(V,E)$ of vertices $V$ and undirected edges $E$. Then a clique is a set of vertices $(v_1,...,v_n)$ such that that there is an edge between any pair $(v_i,v_j)$ of vertices ...
5
votes
3answers
79 views
Why can't set cover be reduced to min-cost max-flow?
Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is.
So, given a universe $U$ ...
0
votes
0answers
11 views
Karp hardness of a module in a graph
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:
For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
0answers
24 views
NP-hardness proof of a model with a convex objective
Let $T=(V,E)$ denote a tree. Each node $j \in V$ in the tree has a known attribute $c_j$.
From T, construct a bi-directional graph $G' = (V, E')$ where $E' = \{(j,k), (k,j)| (j,k) \in E\}$. Simply, ...
0
votes
0answers
65 views
A Language in CNF with distinct variables per clause and each variable appears in at most three literals is in P
Let A be a language defined thus
A = {φ | φ is in CNF, with three literals, comprising distinct variables, per clause;
and each variable appears in at most three literals; and φ is satisfiable} .
...
0
votes
1answer
33 views
NP Completeness of a Graph Problem, Proof Required
I have a graph problem that I would like to prove NP-completeness. It is outlined below:
A graph problem compromising of two graphs, say $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ such that $V_i$ and $E_i$ ...
0
votes
1answer
33 views
Why is showing that ILP in NP not trivial
I have a question regarding the topic of showing that ILP is in NP
What is the problem with Guess and Check?
Guess a solution and then check if it is optimal.
Or further:
Calculate a solution via ...
1
vote
1answer
35 views
Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?
I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?
0
votes
1answer
23 views
Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$ [closed]
How to solve Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$? Can I simply say it is in $O(N!)$?
2
votes
1answer
32 views
GI-Completeness of graph isomorphism with connected graphs
The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
1
vote
0answers
56 views
How to prove a submodular maximization problem is NP-hard
We know that a submodular maximization problem of the form
$$
\mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right)
$$
where $f(S)$ is a submodular set function, is NP-hard (Claim 1).
This ...
3
votes
1answer
126 views
Properly stating a decision problem for a Hamiltonian cycle problem
I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
0
votes
0answers
36 views
Proof for correctness of reduction from 3-SAT to quadradic equations NPC problem
A reduction from 3-SAT to quadratic equations is described as follows:
Given an input expression to 3-SAT, convert it to a quadratic example as follows:
$x_i \rightarrow ax_i$
~$x_i \rightarrow a(1-...
1
vote
1answer
70 views
Does this solve boolean satisfiability problem in polynomial time?
CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
3
votes
0answers
33 views
Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix
I am trying to find a solution (or algorithm) for the following combinatorial problem:
Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
0
votes
0answers
124 views
how to convert SAT to 3SAt
My teacher showed these steps when converting SAT to 3SAT (he was working with an example).
He said to construct a formula F1
...
0
votes
0answers
26 views
NP-hardness of finding the zero norm of a sparest null vector
The abstract of the paper The Null Space Problem I. Complexity states that finding a sparsest null vector of a matrix with more columns than rows is NP-hard (actually NP-complete). I wonder whether ...
0
votes
1answer
45 views
If a NP-complete problem is not in P, then all NP-complete problems are not in P?
It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P.
But, is it also the case that if a NP-Complete problem ...
0
votes
0answers
20 views
USAT, Arora Barak's book
Here on the page 354 Arora and Barak write below the shaded area
"but in fact $f(\phi)$ $\notin SAT$"
and not
"but in fact $f(\phi) \in SAT$"
While in the last line of the shaded area they write
$...
0
votes
0answers
36 views
minimize system of infinity norm of polynomials
I have a problem that looks like this:
set of expressions of the form:
$p_i = ax_{i}+bx_{i}^{\frac{2}{3}} $ for $ 1 \leq i \leq n$
and I'm trying to find $ min_{\Sigma x_i=G}\{max_{1\leq i \leq n}|...
0
votes
1answer
43 views
Showing NP-completeness of a variant of the assignment problem
Suppose we have $k$ jobs, $J=\left\{ j_{1},\ldots j_{k}\right\}$ and $n$ agents, $A=\left\{ a_{1},\ldots a_{n}\right\} $. Each assignment has associated with it a subset of agents which can perform ...
1
vote
0answers
49 views
Is $k$-rainbow coloring of a hypergraph NP-complete or not?
A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. The problem is also called "polychromatic coloring"
Is $k$-...
6
votes
0answers
222 views
Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete? [closed]
Question
I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete.
Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$.
Where $\...
0
votes
1answer
109 views
Alternating hamiltonian cycles is in NP-complete
• Alternating-Hamiltonian-Cycle: Given a graph G = (V, E), and a subset A ⊆ V of its vertices,
does there exist a Hamiltonian Cycle of G, such that the cycle alternates between vertices in A and
...
3
votes
1answer
31 views
Team Ranking Model vs Graph Theory Model
Suppose we have $4$ sports teams, $\{T_1, T_2, T_3, T_4\}$, and we have to following records:
$T_1$ beat $T_2$ by a score of 4
$T_1$ beat $T_4$ by a score of 2
$T_2$ beat $T_3$ by a ...
2
votes
1answer
180 views
Why Hamiltonian cycle decision problem in NP-complete?
I was reading the algorithm book of Neapollian and Naeempoor and it says Hamiltonian cycle decision problem is np complete and CNF can be reduced to it .I understand that why it is NP but i want to ...
0
votes
0answers
37 views
Polynomial time reduction mapping for coNP
We know that the following statement is true for NP and P classes.
A≤pB and B∈P, then A∈P
But is this statement also true for co-NP languages?
is the trick of ...
0
votes
0answers
32 views
Knapsack as a dynamic programming problem
Ok so we are given the following linear programming problem:
$\max x_1 + 2x_2+2x_3+3x_4$
Subject to:
$2x_1 + 3x_2+x_3+2x_4 \le 4$
$1x_1 + 2x_2+ 3x_3+x_4 \le 4$
$x_1,x_2,x_3,x_4\in {0,1} $
My ...
0
votes
0answers
35 views
Where i can find example of ant colony method for knapsack problem?
I could not find example of solving the problem of a backpack by the method of an ant colony. Has found only the description of a method. If you know where to find please help.
2
votes
1answer
141 views
Famous convex maximization problems
Which are the most famous problems having an objective of maximizing a nonlinear convex function (or minimizing a concave function)? As far as I know such an objective with respect to linear ...
2
votes
1answer
42 views
Create a circuit based on a graph
Let's say I have a graph,
and from this graph I want to create a circuit $K$ whose inputs can be set so that $K$ outputs true iff the graph has an independent set of size $\ge2.$
I've seen some ...
1
vote
1answer
78 views
Determine the independent sets of size 2 of G
So lets say I have a graph..
and I want to find the independent sets of size 2. I'm a little confused on how to go about this.
I know that a Independent set if there are no edges between vertices in ...
0
votes
0answers
11 views
Maximize vertex cover weights with bounded edge weights in a connected subgraph
In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximal. Is this problem ...
0
votes
1answer
66 views
Reducing 3 SAT to max 2 SAT
In the reduction done here, you take one clause $d = a \cup b\cup c$, and make 10 clauses
$a, b, c, d, a \cup \neg d, b \cup \neg d, c \cup \neg d, \neg a \cup \neg b, \neg b \cup \neg c, \neg a \cup ...
0
votes
0answers
100 views
NP-completeness certificate of a Hamiltonian path
A Hamiltonian path is a path in a directed , edge positive valued finite graph which visits every vertex exactly once and returns to the original vertex.
This should be a NP-complete problem, but I do ...
