Questions related to NP-hardness and NP-completeness.

learn more… | top users | synonyms (1)

6
votes
0answers
136 views

Complexity of sum of max subset products

Suppose we are given a sequence $x = (x_1, x_2, \cdots, x_n)$ of $n$ rational numbers, where $x_i \ge 1$ for all $i$. Recall that $[n]=\{1,2,\cdots,n\}$. For each subset $I \subseteq [n]$, let $G(x, ...
2
votes
1answer
77 views

Set cover with budget on sets

I am wondering if this is a studied variant of the Set Cover problem. We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$. We want to cover all elements in ...
6
votes
1answer
127 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 ...
-3
votes
0answers
85 views

Is finding the longest cycle in a directed graph vs undirected graph NP hard? [closed]

To find the girth or the shortest cycle in a directed/undirected graph one can for edge edge, remove it from the graph and find the shortest distance between the end points. The shortest such distance ...
1
vote
2answers
192 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 ...
6
votes
3answers
225 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 ...
-4
votes
0answers
16 views

Partitioning NP-complete problems [migrated]

Let's suppose I have an NP-complete problem A. Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete? My guess would be yes. ...
1
vote
0answers
49 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 ...
5
votes
1answer
107 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
83 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
128 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$ ...
2
votes
0answers
96 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 ...
5
votes
1answer
287 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 ...
3
votes
0answers
56 views

another solution problem (ASP) of integer multicommodity 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" (http://dl.acm.org/citation.cfm?id=1382492) that any SAT ...
2
votes
1answer
57 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 ...
9
votes
7answers
412 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), ...
13
votes
0answers
284 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
157 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
228 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 ...
2
votes
2answers
70 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 ...
13
votes
4answers
405 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” ...
28
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 ...
14
votes
6answers
1k 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
540 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
309 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
109 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 ...
16
votes
2answers
482 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
169 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 ...
4
votes
1answer
151 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
210 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 ...
3
votes
1answer
242 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? ...
5
votes
1answer
223 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 ...
24
votes
3answers
787 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 ...
9
votes
2answers
196 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
196 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
126 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
193 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 ...
2
votes
1answer
194 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 ...
18
votes
3answers
834 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
133 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 ...
6
votes
1answer
348 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 ...
9
votes
3answers
420 views

Exact Algorithms for Dominating set

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 ...
8
votes
1answer
240 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 ...
1
vote
2answers
258 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$ ...
9
votes
1answer
155 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
205 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
290 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, ...
5
votes
1answer
258 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$ ...
6
votes
1answer
399 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 ...
2
votes
0answers
123 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 + ...