Questions related to NP-hardness and NP-completeness.

learn more… | top users | synonyms (1)

8
votes
1answer
126 views

“Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
7
votes
1answer
319 views

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
6
votes
0answers
78 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
0
votes
0answers
56 views

Assign undirected edges in a mixed graph to make graph cyclic/acyclic [migrated]

What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph cyclic. What about to ...
2
votes
2answers
160 views

Balls & Bins: A punishment and reward game

Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows: (1) Once a bin has a ...
2
votes
0answers
61 views

Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
6
votes
0answers
47 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
9
votes
0answers
97 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of ...
0
votes
0answers
45 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have n cannisters that must go into m trucks that can each carry k cannisters. You require that no truck becomes overloaded, and for each cannister, there is a ...
-1
votes
0answers
82 views

NP-hardness of the following problem

A subgraph $H \subseteq G$ is said to be 'valid' if all the paths in $H$ satisfy the property $x$. The property $x$ is closed under taking sub-paths. Given a directed graph $G$ and a set of all ...
2
votes
0answers
60 views

Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
1
vote
0answers
44 views

Bounding the cost of an approximation algorithm when subtraction involve [closed]

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound ...
4
votes
2answers
113 views

Variation on partial Set Cover with penalties

I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem: Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup ...
0
votes
0answers
58 views

Minimum Weight Ordering of nodes on a directed graph

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be) Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. The ...
0
votes
0answers
46 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
4
votes
1answer
115 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the ...
10
votes
1answer
295 views

Probability of generating a desired permutation by random swaps

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list ...
6
votes
0answers
200 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
1
vote
1answer
85 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
1
vote
0answers
133 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
0
votes
1answer
120 views

Hardness of an extended maximum set packing problem

(Edited) The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$. The requirement in this problem is that the sets in the solution will be ...
2
votes
1answer
122 views

Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem: Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' ...
12
votes
2answers
1k views

Hamiltonian cycle on graphs without small cycles

While answering this question on cstheory, I (informally) proved on the fly the following theorem: Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if ...
6
votes
0answers
84 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
5
votes
0answers
166 views

NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?

I am trying to learn about some techniques that are used for proving the NP-completeness of domination related problems. One of the problems that is known to be NP-complete is the domination number of ...
3
votes
1answer
286 views

Hardness of 3-dimensional matching variant

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
1
vote
0answers
75 views

NP-hardness of a bilinear program?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$. I have the following bilinear program: max $\sum_{i=1}^n (x_i-a_i)y_i$ ...
2
votes
0answers
118 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
1
vote
0answers
50 views

Help in NP-Hardness proof of a certain type of Class Cover problem

Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) ...
2
votes
1answer
116 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 ...
7
votes
1answer
253 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
231 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
370 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
58 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 ...
6
votes
1answer
254 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
89 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
136 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$ ...
3
votes
0answers
178 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
333 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 ...
4
votes
0answers
104 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
73 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 ...
19
votes
9answers
887 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), ...
17
votes
1answer
477 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
168 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
356 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
74 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
604 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 ...
16
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
592 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 ...