Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...