Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
0
votes
0answers
12 views

NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
2
votes
0answers
29 views

Disjoint paths in digraphs is NP-complete

In the article: S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121. link: https://www.sciencedirect.com/science/article/pii/...
0
votes
1answer
35 views

In which paper is written that you can transform one problem to another to show NP-completeness?

For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post I am searching for a scientific paper to cite where it is written, that ...
1
vote
1answer
52 views

An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
2
votes
1answer
40 views

Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
4
votes
1answer
88 views

Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
4
votes
2answers
2k views

Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...
0
votes
1answer
69 views

triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
2
votes
1answer
55 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
3
votes
1answer
45 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
0
votes
2answers
124 views

What is wrong with the following $P$ problem?

Our teacher gave us the following statement and we were wondering what is wrong with it. Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check ...
6
votes
4answers
3k views

How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
1
vote
1answer
48 views

Independent set problem

I'm referring to a post here,https://www.transtutors.com/questions/suppose-that-someone-gives-you-a-black-box-algorithm-a-that-takes-an-undirected-grap-1706946.htm# Question: Suppose that someone ...
1
vote
1answer
2k views

A problem in NP but not NP-complete?

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
2
votes
0answers
24 views

On the hardness of constraint satisfaction

I am interested in the hardness of the following question. Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\...
0
votes
0answers
39 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
0
votes
1answer
28 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
3
votes
1answer
125 views

maximum coverage version of dominating set

The dominating set problem is : Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
1
vote
0answers
12 views

What is the FPTAS algorithm to find flow at each link for multi commodity flow problem?

I have a graph and K commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodity and the relevant paths. I understand the problem in ...
1
vote
0answers
24 views

Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
1
vote
1answer
46 views

Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts

The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,...
4
votes
0answers
24 views

Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
0
votes
1answer
20 views

Clarifying what it means to be Strongly NP-Complete

Wikipedia defines strongly NP-Complete as: A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
0
votes
0answers
31 views

How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
1
vote
1answer
121 views

Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...
0
votes
1answer
58 views

On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
3
votes
2answers
87 views

Coloring an interval graph with weights

I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
1
vote
1answer
74 views

Non-constructive $NP$-completeness proof

Is there any known $NP$-complete problem which hardness proof is non-constructive. A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument ...
2
votes
1answer
64 views

Is SAT a single language or a union of languages?

I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
4
votes
1answer
48 views

Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
4
votes
2answers
57 views

Given a set, partition it into ordered triples

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$. The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$? I was trying to ...
9
votes
2answers
175 views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
1
vote
1answer
41 views

Encoding order relations in CNF

I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in ...
3
votes
3answers
162 views

You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover ...
0
votes
0answers
14 views

Which instances of Exact Cover are considered hard?

In the Exact Cover formulation there are $N$ variables and $M$ "clauses''. For the special case when each clause contains exactly $3$ variables it is called 3-Exact Cover. Now, I've read in articles ...
4
votes
2answers
2k views

What is the simplest known NP-Complete problem for testing P=NP solutions? [closed]

About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic....
0
votes
1answer
73 views

P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
0
votes
1answer
65 views

Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
2
votes
2answers
176 views

Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
0
votes
1answer
75 views

NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
2
votes
2answers
223 views

How to prove LastToken problem is NP-complete

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...
0
votes
0answers
58 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
1
vote
2answers
54 views

Prove the Droid Trader Problem is NP-complete

This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos. A player in the game controls a spaceship and is trying to make money buying and selling droids on ...
1
vote
1answer
36 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
2
votes
1answer
45 views

Finding a vertex coverage that is also an independent set

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
-1
votes
1answer
33 views

Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
1
vote
1answer
51 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
1
vote
0answers
20 views

Show that SQUARED-SUM-PARTITION is NP-complete

Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$, and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ ...
0
votes
1answer
34 views

Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
1
vote
1answer
31 views

NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...