Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
0
votes
0answers
11 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
8 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
votes
0answers
11 views
delete some rows of a matrix
"delete k rows from a matrix and then sum each column, say the sum vector is c whose length is number of columns, we want to make sure that at least 5 elements in c is bigger than zero.
The question ...
1
vote
1answer
59 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
31 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
25 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
56 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
20 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
62 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
31 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
25 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 ...
0
votes
0answers
47 views
Maximizing absolute values in LP - practical applications
It is NP-hard to maximize absolute values with respect to a polyhedral set of constraints. The reason is that the objective is then a convex function and we maximize it. Since the constraints are ...
1
vote
1answer
33 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
30 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
42 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
110 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
20 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
40 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
31 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
32 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
21 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
36 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
19 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
25 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
37 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
42 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
217 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
102 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
30 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
71 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
35 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
31 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
31 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
87 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
39 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
61 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
10 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
46 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
80 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 ...
1
vote
0answers
135 views
Travelling Salesman Problem Nearest neighbor heuristic
One criticism of the nearest-neighbor TSP heuristic is that the last edge added (from the last city back to the starting city) can be very long. How much effect can that last edge have on the ratio NN/...
-2
votes
1answer
47 views
Can a completely non-brute algo exist for solving Sudoku given it's NP-complete? [closed]
As far as I understand it, Sudoku is an NP-complete problem and the best known algorithm for solving it would therefore scale exponentially with grid-size, N.
All the algorithms I have so far seen ...
3
votes
1answer
80 views
Rules for Reductions in NP-Completeness Proofs (many-one vs one-many)
My understanding is that when reducing one problem known to be NPC (e.g., HAM-Cycle) to another problem known to be NP (e.g., Ham-Path) we have shown that the second problem (the target of the ...
1
vote
0answers
55 views
Rainer Schuler's algorithm of CNF SAT problem
I'm reading through this publication trying to understand the algorithm and what exactly did Schuler achieve compared to Cook's theorem.
Can someone please explain me how this algorithm works in ...
0
votes
0answers
9 views
Is h(f(g(x))) NP-hard if g and h is NP-hard and f is Polynomial time solvable
Given two different problems $g$ and $h$ both of which are proven to be NP-Hard. We assume size of solution is not deducible from the size problem for both $g$ and $h$ (So $g$ and $h$ are not decision ...
1
vote
0answers
55 views
Is Threshold Logic Minimization (synthesis) NP-Hard, NP-Complete or NP or..
Consider a problem of generating a minimal threshold logic circuit for an arbitrary boolean function. This is akin to usual circuit optimization, but gates are allowed to be any threshold (linearly ...
1
vote
2answers
41 views
Euclidean Case of the TSP for a given problem.
My textbooks states that the "Euclidean Plane" case of the Traveling Salesperson Problem is a special case of the TSP, when all the points lay in the euclidean plane and the distance between these ...
1
vote
0answers
50 views
Can't understand this statement
I was reading some bachelor thesis and it mentioned reducing the hitting set problem to the set cover problem. However I am unable to understand the last line in the referenced paragraph, I would ...
1
vote
2answers
337 views
P/NP reduction (hamiltonian cycle to TSP)
I have a P/NP question.
I have read that were any NP problem be found to have a polynomial time algorithm, then we can reduce any other NP problem to a form where we can use our first algorithm to ...
