Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

-3
votes
0answers
37 views

Does P=NP? (The big question) [closed]

If you know much about theoretical computer science, you have heard the question before. This site has plenty of questions posted about the implications of one answer or another to this question (...
2
votes
1answer
42 views

How to partition a set in order to minimize the number of the elements and their interactions?

Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
3
votes
0answers
73 views

A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
1
vote
0answers
21 views

Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset

Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
2
votes
1answer
49 views

Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]

The following variation on the vertex cover problem was given: Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$? I was asked to prove that ...
1
vote
1answer
52 views

Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
2
votes
1answer
41 views

Reducing 3SAT to a Set Splitting Problem

I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the ...
3
votes
1answer
35 views

How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?

I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head. FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture ...
2
votes
2answers
137 views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
0
votes
1answer
30 views

Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
0
votes
1answer
70 views

Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
46 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
35 views

Finding a suitable NP-complete problem for reduction

We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
1
vote
1answer
31 views

Why Cook-Levin thorem's proof can mean SAT's NP-Hardness

I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ ...
0
votes
0answers
36 views

Why finding out an independent set of size k is in NP-C and not in P? [duplicate]

I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P. P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is ...
1
vote
2answers
30 views

NP-hardness does not imply lower bound, strictly speaking?

A problem is NP-hard iff every NP problem can be polynomially-time reduced to it. Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
3
votes
1answer
41 views

Proving NP hardness about graph creation problem with triangle number

I have graph creation problem. Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
2
votes
1answer
71 views

Max flow and Matching problem

Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
2
votes
0answers
23 views

Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
0
votes
0answers
21 views

Finding if a given problem is a Np-Hard problem - recruitment problem

I have to prove that the following Recruiting problem a NPC-problem. Input: n candidates and m positions and a matrix A $\in {Q^{n\times n}}$. Each entry $A_{ij}$ with i < j tells how much gets ...
1
vote
2answers
98 views

How to generate an instance for an NP_hard proof, where each element has two inputs?

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
1
vote
0answers
24 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?
0
votes
1answer
33 views

Graph Edit Distance

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition. Link: https://www.springer.com/cda/content/document/...
1
vote
1answer
64 views

Reducing subset sum to even subset sum

I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
0
votes
1answer
30 views

Karp reduction from NP-hard problem to unknown problem

If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true: $$A \to B \, .$$ Is it correct to conclude that $B$ must also be NP-hard?
6
votes
2answers
1k views

Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly. And then, I realized that it is not certain where undecidable problems should be placed. ...
0
votes
1answer
63 views

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

What is the complexity of this problem EULERIAN ARC REVERSAL Input: a directed graph $G(V,A)$ and an integer $k$ Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
1
vote
0answers
20 views

Proof that MAX-2-SAT is NP-hard [duplicate]

According to Wikipedia, while the 2SAT problem is polynomial, its maximization variant MAX2SAT is NP-hard. But, they do not provide a reference for this claim. Is this obvious? If not, where can I ...
2
votes
1answer
24 views

NP-Hard on Complete Graphs

I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
1
vote
1answer
158 views

Gerrymandering Problem: Variant on Set Partitioning

I was recently helping a friend with homework from a dynamic programming class, and this was the question: Given a set of n precincts P1 ,... Pn , each containing m votes, with <...
1
vote
1answer
34 views

Variant of an approximation algorithm for vertex cover

Here is an approximation algorithm that finds vertex cover of a graph. ...
0
votes
1answer
147 views

How can I show that a problem is not $NP$

Consider the following image: The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$. I ...
0
votes
1answer
65 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
1
vote
2answers
87 views

If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

I came across this question while studying for an exam: T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ ...
1
vote
1answer
25 views

Complexity of two cycles which differ by $1$ in length

Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length. What is the complexity of this problem?
2
votes
1answer
60 views

Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?
2
votes
1answer
34 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
2
votes
3answers
601 views

What will happen to NP-Hard problems if P=NP

I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class. He further said that if we can ...
1
vote
1answer
51 views

Karp hardness of directed monochromatic triangle problem

Monochromatic problem is a classic NP-complete problem. Does the complexity stay NP-complete if we use directed graph? DIRECTED MONOCHROMATIC TRIANGLE problem: Input: A digraph $G(V,A)$ ...
1
vote
1answer
60 views

Is this an $NP$-complete problem: Product-2-Partition

I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say PRODUCT-2-...
0
votes
0answers
10 views

Karp hardness of a supportive clique in digraphs

In a directed graph (digraph) $G(V,A)$, a set of vertices $C\subseteq V$ is called a supportive clique if (1) for every $u\neq v$ in $C$, either $(u,v)\in A$ or $(v,u)\in A$ and (2) for every $u\in C$,...
0
votes
1answer
21 views

Karp hardness of a diameter-decreasing planted clique

A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}...
1
vote
1answer
47 views

For each given set choosing either it or its complement such that their union exactly has a given size

Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
0
votes
1answer
48 views

Karp hardness of a clique with given number of outer-incident edges

A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$. Given a clique $\mathcal{C}\subseteq ...
3
votes
0answers
42 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)=\...
0
votes
1answer
41 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
1
vote
2answers
68 views

Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$...
1
vote
1answer
39 views

Karp hardness of a vector system allocation

Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
1
vote
1answer
33 views

Karp hardness of a guarding set in digraph

Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following. A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
1
vote
2answers
48 views

Karp hardness of digraph coloring without monochromatic dicycle

Problem statement: Input: a digraph $G(V, A)$ and a natural number $k$ Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, ...