Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 $...
user avatar
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 (...
user avatar
-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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ".....
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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)$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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: $...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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'...
user avatar
  • 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}$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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} \...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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/...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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$ ...
user avatar
  • 402

1
2 3 4 5
13