Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
1
vote
1answer
29 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
21 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
33 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
101 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
9 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
votes
0answers
19 views
Proof/Disproof NP-Completeness: Project Problem
i am currently working on a problem and i am pretty stucked. I need to proof or disproof whether a given problem is np-complete.
Given the following project problem.
There are $n$ departments $\...
1
vote
1answer
34 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
26 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
25 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
20 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
32 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
18 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
24 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
35 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
38 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
214 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
98 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 ...
1
vote
1answer
40 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
28 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
61 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
36 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
46 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
40 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
74 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
121 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
40 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
72 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
52 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
45 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
38 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 ...
0
votes
0answers
46 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
303 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 ...
0
votes
0answers
28 views
Reduction from an assignment problem to Independent Set. Show NP-complete/ hard
The problem I have is as follows:
I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$
The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C ...
0
votes
0answers
100 views
Generalize minimum path cover
Let $G=(V,E)$ be a directed acyclic graph (DAG). A vertex $u$ reaches a vertex $v$ if there is a directed path from $u$ to $v$. Let $R \subseteq \{ [v_i, v_j] | v_i,v_j \in V$ and $v_i$ reaches $v_j\}$...
7
votes
1answer
95 views
Find a generalized path cover of a square graph
Given a directed $n\times n$ square graph as shown in the figure with $n^2$ nodes. Find a set of directed paths $\mathcal P$ from $s$ to $t$ with the minimum cardinality (i.e, minimum number of paths ...
1
vote
1answer
41 views
Categories with at most one arrow between any pair of objects. (appears in NPC)
Motivation. I was reading about P vs. NP and I found Cook-Levin thm, which states that any NP problem can be reduced in polynomial time to some SAT. (As I just learned, this means precisely that SAT ...
1
vote
0answers
21 views
Integer Programming (non $0-1$) Reduction to show $NP$ Completeness
I'm having trouble coming up with a reduction for the integer programming problem when the variables aren't constrained to $0$ or $1$. For the case where the variables are constrained to $0$ or $1$, ...
1
vote
0answers
175 views
Show the NP completeness of Hamiltonian Path with the knowledge of an directed Euler graph
I'm interested in the idea behind a NP completeness problem. It should be checked that Hamiltonian Path is in NP. As an indication, the problem Euler graph is in NP.
Definition of Euler graph: An ...
2
votes
0answers
36 views
How should a chain of proof be written?
I have a to prove problem $P_{2}$ is NP-Complete. But for that I need to prove another intermediate problem $P_{1}$ NP-complete too. To prove $P_{1}$ I need to state that problem $P_{0}$ is already ...
0
votes
0answers
37 views
Minimise the sum of pairwise distances between labelled points in a metric space subject to covering some set of labels
I would like to know the name of the following problem. I assume it is NP-hard, but a link to a proof of such would also be appreciated.
Say we have some set of points in a metric space $S = \{p_1,......
1
vote
1answer
101 views
Bipartite Graph Partitioning (special case)
In the course of my research, I came across a graph matching problem for bipartite graphs, and I am wondering if this particular problem has appeared in the literature before. I suspect it is NP-...
1
vote
0answers
40 views
Linear Programming Primal-Dual tough question
A tough question me and a friend are facing:
G=(V,E) undirected graph.
s∈V a source vertex.
each v∈V has a value dv>=0.
each e∈E has weight (capacity) ce>=0.
Pv is a Path:s---->v from the source to ...
0
votes
0answers
52 views
Show that SSHP is NP Complete
Short version: How can be shown, that SSHP is NP complete?
DEF: SSHP, is defined by an undirected graph. Is there a path from
a to b that every node is passed. a and b are elements of nodes.
$$ G(V,...
1
vote
2answers
345 views
Divide set into two subsets of equal sum and maximum this sum
Original Question: https://stackoverflow.com/questions/47492444/create-two-sub-lists-from-given-list-of-integers-with-equal-sum-and-maximize-thi
You are given a list S of positive integers. You are ...
