Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
620
questions
0
votes
0
answers
9
views
What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?
As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
- 619
0
votes
1
answer
33
views
Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?
I think we should be able to say that $R$ is in NP since an instance of $...
- 2,238
0
votes
1
answer
32
views
Checking NP-completeness of the following problem(s)- Assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. Suppose each department $d$ is considering hiring some $C_d \subseteq \{1, 2, ... n\}$ candidates (...
- 1
-1
votes
0
answers
38
views
How relevant would it be to prove that P vs NP is equivalent to P vs NP using only machines with one letter input alphabet?
I was reading the official description of P vs NP at https://www.claymath.org/sites/default/files/pvsnp.pdf out of curiosity and the authot says
"Does $\textbf{P = NP}$?
It is easy to see that ...
- 123
0
votes
0
answers
24
views
Christofides Algorithm for the TSP: A "polynomial time approximation algorithm"?
I'm currently studying the travelling salesman problem and Christofides algorithm. I think I understand that TSP is an NP-hard problem, and so the complexity of calculating a solution grows ...
- 197
1
vote
1
answer
31
views
Finding 2 edge disjoint perfect matching in a bipartite graph
Is it NP-hard to decide if an arbitrary bipartite graph has 2 edge disjoint perfect matchings? It is hard for cubic graphs, but I am not sure whether it is still hard for bipartite graphs.
- 43
0
votes
2
answers
62
views
How to prove that 2SAT $\in$ P
I want to understand the proof in the following link for 2SAT $\in$ P...
What for the need of the last corollary?
Wouldn't be enought to just prove the case for the graph with the help of the path ...
- 17
2
votes
1
answer
28
views
Maximum flow with minimal number of vertices used
In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
- 43
2
votes
3
answers
371
views
Why is it so difficult to prove $\mathbf{NP} ≠ \mathbf{P}$?
I'm just curious because I saw on Wikipedia a single polynomial time solution to any NP-hard problem would imply there are polynomial time solutions for every single NP problem.
Also I assume there ...
- 283
0
votes
2
answers
29
views
Proving NP Completeness of "the project manager's problem"
Suppose we have a list of basic/'atomic' tasks $\{p_1, ..., p_n\}$ and each task has an associated cost $c_i$ for all $i \leq n$.
Morover, we have a list of projects $P_1,..., P_m$ which are ...
2
votes
0
answers
78
views
Finding a biggest (in terms of dimension) vector space in a finite set
I previously asked a similar question to this but noticed that the formulation was slightly different than what I am interested in, therefore I ask for any useful information on this problem (by any ...
0
votes
1
answer
104
views
Checking if a matrix is zero deletable?
Given a matrix $\in [0,1]$. Delete operation is defined as: If one of the elements of the matrix contains 1 or 2 it can be deleted and replaced by 0.
A matrix is zero deletable if there is a chain of ...
- 3
0
votes
0
answers
33
views
Proving That Finding A Flow that Saturates k Edges is NP Complete Via Reduction to Subset Sum Problem
Let's say there is a flow network called G and a flow in G called f, we say that f saturates an edge e if the flow value on that edge is equal to its capacity. The flow sat problem is: given a flow ...
7
votes
1
answer
250
views
Finding a maximal vector space in a finite set
Let $X \subseteq \{0,1\}^n$ be a nonempty set of vectors of length $n \geq 1$ with binary components such that the zero vector $\vec{0}$ having all components equal to $0$ belongs to $X$. Along with ...
4
votes
1
answer
122
views
Does this comment from Stephen Cook on p-np problem has support from others?
It is kind of odd to ask for a credibility of a comment from someone who invented the field, but let me introduce one of Stephen Cook's comments supposing when the situation comes out as p=np.
".....
- 331
1
vote
1
answer
71
views
Unclear about the definitions of $P$ and $NP$
I am trying to build my intuition about the np-completeness problem.
As I understand, it is well-known that there are problems that are neither $P$ nor $NP$.
Here is an example of a problem that is ...
- 9,771
0
votes
0
answers
25
views
What families of graphs is the subgraph isomorphism problem known to remain NP-complete?
The subgraph isomorphism problem consists of two graphs, G and H and asks if there is some subgraph of G that is isomorphic to H. There are several families that H can be sampled from that preserve ...
- 31
1
vote
2
answers
64
views
Finding a subgraph satisfying degree constraints in a directed graph
We are given a directed graph $D=(V,A)$ and two values $i(v)$ and $o(v)$ for each vertex. Is it NP-hard to find an induced subgraph of $D$ such that the in degrees are at most $i(v)$ and the out ...
- 43
0
votes
1
answer
51
views
Why doesn't Krom's method apply to solving the 3SAT in polynomial time?
In the paper "The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary", Krom suggested a method to solve 2SAT problem.
My understanding is this.
Use ...
- 13
0
votes
0
answers
18
views
Np-compleness of a string problem
Given a language $L$ that contains many strings. We want select some strings $S$ from $L$ such that symbol $a$ repeated in $S$ $k$ times. How it possible to that problem is Np-complete? I think we can ...
- 1
1
vote
1
answer
47
views
Maximal Disjoint Subset of Collection of Open Sets
Given a collection of open sets, $S$ in some topology, is there a canonical way to find a maximal subset $S' \subset S$ such that all elements of $S'$ are mutually disjoint? I am particularly looking ...
- 3,801
0
votes
0
answers
125
views
Prove that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete
I want to prove that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is $\mathcal {NP}$-Complete as well.
Sparse Subgraph problem:
Input: An undirected graph $G(V,E)$, ...
- 414
0
votes
0
answers
38
views
Does a zero knowledge proof require the verifier to agree, after the proof protocol is completed, that the question/statement has in fact been proven?
Trying to understand the results and implications of zero-knowledge proofs: do we assume that the verifier simply has to accept the results (provided the protocol is carried out correctly)? What if ...
- 51
1
vote
0
answers
26
views
How much running time does solving a Mixed Integer Linear Program need?
Given a mixed integer linear program with $m$ constraints and $n$ variables how much time do we need to solve this?
I know that MIPs like IPs are in general NP-hard. Nevertheless for IPs one can show ...
- 578
0
votes
0
answers
21
views
traffic assignment
Here are $m$ cities $C_1,\cdots,C_m$. The road connecting $V_i$ and $V_j$ is denoted as $E(i,j)$. Now there are $n$ trains $T_1,\cdots,T_n$. For each train $T_i$, it corresponds to two parameters: $...
- 9
0
votes
0
answers
96
views
I need to prove that this Harry Potter problem is NP-Hard. To what problem can it be compared for reduction?
Harry Potter is looking for a bowtruckle that is hiding in a graph and has made
itself invisible. Harry tries to find the bowtruckle by casting the spell rivilio trullio while aiming his
wand at a ...
- 1
2
votes
1
answer
56
views
Understanding our prof's definition of P vs NP
(I have read a lot of online articles, including on MO, SO, etc. but my question stays)
We have the following definitions:
...
- 449
0
votes
0
answers
9
views
Prove that specific language L is NP-complete and that L $\leq _p$ 3-Colorability
Let $\phi$ be a 3CNF-Boolean formula. An $\neq$-assignment to the variables of $\phi$ is one where each clause contains two literals with unequal truth values. In other words, an $\neq$-assignment ...
- 1
4
votes
1
answer
349
views
How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?
The subset sum problem is as follows:
Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose ...
- 41
0
votes
1
answer
51
views
Variant of Clique Problem
Given a graph $G$, we say a subset of vertices $S$ is a "good" clique if $S$ itself is a clique and for any vertex $v \in G$, there is a vertex $u \in S$ such that $v$ is adjacent to $u$. I'...
- 1,466
1
vote
0
answers
14
views
NP-hardness via polynomial time reduction
I am trying to show a decision problem is NP-complete, using a polynomial-time reduction. As this is a homework question I won't post the exact question but the gist is this:
"Let $k\in\mathbb{N}$...
- 25
0
votes
0
answers
17
views
Prove NP-completeness of Connected Vertex Cover Problem
Connected Vertex Cover problem is to determine whether a (undirected) graph $G = (V,E)$ contains a $k$-vertex cover $V′$ with $G[V′]$ connected.
I know to prove its NP-completeness requires finding ...
0
votes
0
answers
167
views
Karp Reducing Between Problem X and Partition Problem To Show NP-Completeness
I am supposed to show that the following problem is NP-complete by Karp reducing it to the Partition Problem. Problem X is:
Given: D vaccine doses, n age groups, a1 to an as input, where age group k ...
2
votes
1
answer
48
views
Why isn't Quadratic Congruences trivially solvable in polynomial time?
The Quadratic Congruences problem asks if for constants $a$, $b$, and $c$, does there exist $x$ such that $x<c$ and $x^2 \equiv a\mod b$?
This problem is known to be NP-complete. However I can't ...
- 151
0
votes
1
answer
44
views
How we reduce NP problems?
Assume that P1, P2,..., Pn are NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
0
votes
0
answers
38
views
Complexity/ polynomial time - If a problem has $x + y - 1 \choose y-1$ possible solutions & each can be evaluated in polytime, is that in P?
I am trying to show the complexity of a problem and each instance's size is defined by parameters $x$ and $y$. For a given instance, I know there are $x+y-1 \choose y-1$ possible solutions. Each of ...
- 11
0
votes
1
answer
89
views
Given this theorem, Why is Subgraph Isomorphism NP hard and not polynomial?
So, I read the following Theorem by Matousek and Thomas:
Given graphs $G$ and $H$, we want to check if there is a subgraph $S \subseteq H$ such that $S$ and $G$ are isomorphic.
Then, if the maximum ...
- 105
0
votes
0
answers
25
views
Bounded-Frequency Minimum Set Cover Problem
Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets.
Can this problem be solved in polynomial time?
Is there a nontrivial upper ...
- 1,211
1
vote
1
answer
65
views
Is this egyptian fractions problem NP-complete?
Given a set of positive integers $\ M=${$\ a_1,a_2,\cdots ,a_k\ $} and a rational number $\ r\ $ , is the following decision problem NP-complete ?
Is there a subset $S\subset M$ with $$\sum_{p\in S} \...
- 78.3k
0
votes
1
answer
73
views
Reduction of hard to easy problem and vice versa
$A\: \leq_m B$ means means $A$ cannot be harder than $B$ that means $B$ is atleast as hard as $A.$
And also I know that "If $B$ is easy then $A$ is easy" and "If $A$ is hard then $B$ ...
user970439
0
votes
0
answers
43
views
Conversion NPH problem reduction
To prove any problem $R$ is NPH then take any known NPH problem $L$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $L$, then prepare another instance ...
user974277
1
vote
1
answer
95
views
Certifier in the subgraph isomorphism problem
In the subgraph isomorphism problem we need to establish a certifier where we can map the edges from induced map to the original map. And it will take polynomial time to achieve.
Does this mean that ...
- 11
0
votes
0
answers
35
views
Are two optimization problems equivalent?
In complexity theory. There are two optimization problems. If decision problems associted with them are all NPC, then we know the two decision problem are equivalent. Are two optimization problems ...
- 11
1
vote
0
answers
113
views
Is (3,3)-NAE-SAT NP-complete?
In this question I assume the following: in either $(i,j)$-SAT or $(i,j)$-NAE-SAT, every clause has exactly $i$ literals, and a given variable appears at most $j$ times in the entire formula. NAE ...
- 59
0
votes
0
answers
26
views
Partition problem with additional constraints
I have read about the partition problem a.k.a. the easiest hard problem. I am currently working on a game where there are, say, 180 players that need to be organized into 30 teams with 6 players in ...
- 585
0
votes
2
answers
50
views
Maximum independent set in a graph versus maximum matching in the line graph
As regards this post Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$ -- and in particular, the comments under this answer https://math.stackexchange.com/a/...
0
votes
1
answer
34
views
Proofing Decide Injective Coloring Problem is NP-complete for perfect elimination bipartite graphs?
So the proof goes like this
For a graph $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, $E=\{e_1,e_2,...,e_m\}$ having a chromatic number $X(G)$ we construct a perfect elimination bipartite graph $H$, using ...
- 45
0
votes
1
answer
172
views
Non-Optimality of First-Fit-Decreasing Algorithm for Bin Packing
The First-Fit-Decreasing algorithm solves the bin packing decision problem for given weights $w_1,\dotsc,w_n\in [0,1]$ and number of bins $k$ in quadratic time. This would mean that the bin packing ...
- 3
0
votes
1
answer
95
views
Is p-dimensional matching with $(p-1)n$ edges NP-hard? What about $3n$ edges? [closed]
Let $p\geq 3$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof):
Let $V_1, ...
0
votes
0
answers
81
views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 402