Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
8
votes
1answer
336 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
2
votes
2answers
338 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist $k$-...
6
votes
5answers
1k views

Multidimensional knapsack STRONGLY NP-complete

Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found ...
1
vote
0answers
70 views

Different hardness proofs w.r.t different classes

Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard). Is there a ...
8
votes
1answer
629 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
-1
votes
1answer
134 views

NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson [1977]). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
7
votes
0answers
163 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
4
votes
0answers
225 views

How does part 5 of the paper “computational complexity of Minesweeper” work?

Marzio De Biasi mentioned this paper in this answer, and that paper's claim in part 5 would appear to resolve my question. However, there seems to be a significant gap in the proof. Even though one ...
7
votes
1answer
764 views

Is it NP-hard to _play_ minesweeper perfectly?

This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen." If there is a way to "lead a perfect player into" such ...
7
votes
0answers
500 views

Another Solution Problem (ASP) of integer multi-commodity flow: is it NP-complete?

I know that integer multicommodity flow is NP-complete. It was proven in On the complexity of time table and multi-commodity flow problems that any SAT problem can be reduced to an integer ...
2
votes
1answer
141 views

Complexity of Haemers' minimum rank

In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph". Tims has a survey of more recent results his thesis. What is the computational complexity of computing ...
22
votes
10answers
2k views

Problems that are easy on unweighted graphs, but hard for weighted graphs

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), ...
21
votes
2answers
928 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
0
votes
3answers
510 views

Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
9
votes
1answer
1k views

Complexity of finding the maximal number of pair-wise disjoint sets

Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-...
2
votes
2answers
94 views

complexity of CSPs with 2-variable constraints and multi-valued variables

(CSP = "constraint satisfaction problem") CSPs for which either the variables are restricted to less than two values or the constraints take less than two inputs are obviously trivial, and Schaefer's ...
15
votes
4answers
1k views

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs. I've seen the question regarding the other way around here “Directed” ...
36
votes
3answers
2k views

Techniques for showing that problem is in hardness “limbo”

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
20
votes
7answers
3k views

NP-hard problems on paths

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to ...
13
votes
3answers
849 views

Transitive feedback arc set (TFAS): NP-complete?

Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to ...
3
votes
0answers
806 views

What's the hardest problem with a non-trivial exact algorithm?

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough. I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
1
vote
1answer
315 views

Hardness of XSAT

The standard NP-hard SAT problem is the problem of Boolean satisfiability of conjunctions of clauses, where clauses are disjunctions of literals. I am interested in the problem of the Boolean ...
18
votes
2answers
779 views

Co-NP-completeness of minimal TSP tour?

This problem came out of my recent blog post, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one? More precisely is the following problem NP-complete: ...
1
vote
1answer
260 views

Complexity of an edit distance problem

Given an array $A[1...n]$ of non-negative integers, we want to transform $A$ into $A'$ such that $|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations. One operation consist of picking ...
5
votes
1answer
571 views

For what k is MAX-2-SAT-k NP-complete?

It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs ...
2
votes
1answer
265 views

Design of exact algorithms for non-local hard problems

In the connected dominating set problem (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent ...
4
votes
1answer
562 views

Does there exist the idea of “RP-complete”, like NP-complete?

NP-hardness and NP-completeness play an important role in complexity theory. My question is, does there exist a language $L$ in RP to which any language $M$ in RP can be reduced in polynomial time? ...
6
votes
2answers
689 views

Edge and vertex fault tolerance in graphs

Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What ...
27
votes
3answers
1k views

Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1

Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\...
10
votes
2answers
732 views

Is Almost-2-SAT NP-hard?

Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant? What about specifically when there's only one such clause?
5
votes
1answer
383 views

Graph partitioning by node deletion

Given an undirected graph and an integer $B$, we ask to find the minimum set of nodes whose removal partitions the generated graph into connected components, each having at most $B$ nodes. We can ...
2
votes
1answer
155 views

Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history “patch” after $t$ iterations

Question description: Consider the problem of finding a minimum $n$-color $k$-state one-dimensional cellular automata (minimizing $k$ for some fixed value of $n$ or vice versa), with communication ...
3
votes
1answer
231 views

Maximize the expected number of “losers” - Is it NP-hard?

I am trying to find a reduction for a problem that seems NP-hard: Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and ...
3
votes
1answer
831 views

Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?

If this is known, can someone point me to a proof? Edit: A QP is essentially a LP with a quadratic objective. That is, it looks like: minimize $\frac{1}{2} x^T Q x + c^T x$ s.t. $Ax \leq b$ It's ...
20
votes
3answers
1k views

NP complete graph problems about structural properties

(This question is a bit of a "survey".) I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural ...
4
votes
0answers
227 views

The weakly NP-complete problems and their associated counting problem

Are there weakly NP-complete problems whose associated counting problem can be computed in pseudo-polynomial time? And if one were to be found (and assuming it is #P-complete), what would be the ...
16
votes
2answers
2k views

Linear diophantine equation in non-negative integers

There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2,...
14
votes
5answers
930 views

Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$...
8
votes
1answer
620 views

Minimum Triangle Covers

Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem. Is this problem ...
0
votes
2answers
490 views

Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

I have the following Equivalent DNF problem: Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$ Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise. $F_1$ and $F_2$ ...
10
votes
1answer
3k views

Monotone bijections between lists of intervals

I have the following problem: Input: two sets of intervals $S$ and $T$ (all endpoints are integers). Query: is there a monotone bijection $f:S \to T$? The bijection is monotone w.r.t. the set ...
13
votes
2answers
248 views

Complexity of computing a densest minor

Consider the following problem. Input: An undirected graph $G=(V,E)$. Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|...
4
votes
1answer
411 views

Is This Scheduling Problem NP-Hard?

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows: Instance: A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-...
5
votes
1answer
338 views

A reachability problem

Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$) polynomial-time computable program. I. Given two strings $x$ and $y$, we want to decide if $y$ can be obtained by repeated applications of $P$ ...
5
votes
1answer
861 views

Weapon target assignment problem

Does anybody know a NP-hardness proof of Weapon-target assignment problem (http://en.wikipedia.org/wiki/Weapon_target_assignment_problem)? Lloyd and Witsenhausen produced a reduction from 3-EXACT-...
2
votes
0answers
142 views

NP-hardness of a winner determination auction

We would need some suggestions for the proof of NP-hardness of an optimization problem. The problem $$ \max_{x_{a,s}} \sum_s \sum_a x_{a,s} q_a \lambda_s \prod_{s' < s} \prod_{a' \neq a} (1 + ...
10
votes
2answers
411 views

Hardness of a subcase of Set Cover

How hard is the Set Cover problem if the number of elements is bounded by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally, Let $\mathcal{U}=\{e_1, \cdots, e_m\}$...
11
votes
2answers
1k views

On the provability of P versus NP

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course ...
1
vote
0answers
265 views

Partially filled jigsaw puzzle with six types of tiles

This is a slight variation of the question Are 'zero-one' jigsaw puzzles NP-complete? asked on cs.stackexchange.com. What is the complexity of the following problem? Input: an $n\times n$ Jigsaw ...
9
votes
2answers
372 views

Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an ...