Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
26
votes
2answers
1k views

Ladner's Theorem vs. Schaefer's Theorem

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, ...
13
votes
1answer
226 views

The complexity of the dominating set problem in specific subclasses of chordal graphs

I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs. A graph is an undirected path graph if it is the vertex-...
10
votes
2answers
681 views

Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
2
votes
2answers
389 views

NP-hard problem on planar unit disk graph

I am curious to know whether there are problems which are np-hard even on planar unit disk graphs. A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we ...
3
votes
0answers
216 views

Ordered routing problem which is NP-hard

All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way. Are there problems which are still np-hard, if one has to visit the ...
23
votes
1answer
1k views

I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)

It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle. Is there a nice gadget that will, ...
0
votes
0answers
739 views

Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
3
votes
1answer
275 views

Is the problem “MIN-SET-PARTITION” an NP-hard problem?

Given a family of sets $F = S_1, ..., S_n$ of elements from a universe $U$, find the minimal integer $k$ for which there is a partition of $F$ of size $k$, such that every two sets in the same ...
4
votes
1answer
234 views

Chromatic number of a particular graph

Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$. Let $S(x)=\{1, \ldots, x\}$. The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices ...
2
votes
1answer
188 views

Hardness of computing circles with max number of lattice points

You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the ...
10
votes
2answers
3k views

What does 'gadget' mean in NP-hard reduction?

This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
15
votes
1answer
894 views

Ranking the Difficulty of NP Hard Problems in Practice

This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard ...
10
votes
2answers
1k views

Minimum True Monotone 3SAT

I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable. But say the number of true variables is a measure of how good ...
6
votes
3answers
1k views

Complexity of a subset sum variant

Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I ...
16
votes
0answers
353 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

I am interested in the following problem. Node Multiway Cut on Planar Graphs with terminals on the outer face Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals ...
3
votes
1answer
2k views

The significance of NP-Hard Problems in Cryptography

I didn't refer any literature but thought this was ideal to get views from people here.. Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can ...
1
vote
2answers
239 views

Two Decision Problems About Graphs — Original Results?

I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell? I don't have easy access to any standard texts that would help me out here. Nor ...
4
votes
2answers
716 views

Stable Marriage with incomplete lists and ties - NP-hardness

According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard. According to [2] a weakly stable matching in a hospital-residents (...
9
votes
1answer
659 views

Proof that sparsest cut is NP-hard

Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut ...
12
votes
1answer
1k views

Unique SAT vs Exactly $m$ models

Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ? I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m&...
8
votes
1answer
313 views

On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not ...
1
vote
0answers
355 views

Hardness of min-max problems

Consider the following min-max problem Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph. ...
0
votes
0answers
337 views

Maximize Covering Minimizing the Overlap

I have this problem: Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ ...
10
votes
2answers
909 views

A variant of Critical SAT in DP

A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$ A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $...
7
votes
1answer
131 views

Complexity of selective network improvement problem

We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ ...
8
votes
0answers
702 views

Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
19
votes
2answers
1k views

Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

In their paper (p. 503) Garey and Johnson remark: ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ......
17
votes
2answers
2k views

Can strong NP-hardness really be shown using plain polytime reductions?

I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I ...
22
votes
2answers
524 views

Relation between hardness of recognition of a graph class and forbidden subgraph characterization

I'm considering graph classes that can be characterized by forbidden subgraphs. If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm ...
2
votes
2answers
463 views

Complexity of a weighted subset selection problem.

I'm currently thinking about a problem I'd like to manage in one of my applications. There is a set of objects $\{A, B, C, D, \ldots\}$. Every object has the same attributes with different values. ...
51
votes
4answers
22k views

Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
4
votes
2answers
494 views

NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
39
votes
3answers
3k views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

This is a cross-post from math.stackexchange. Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $...
2
votes
0answers
391 views

Post Correspondence Problem “binary” variant

Bounded Post Correspondence Problem is defined as follows: given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...
2
votes
1answer
236 views

Does there exist polytime algorithm for this partitioning problem?

I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling ...
1
vote
0answers
1k views

A variation of the subset sum problem [closed]

The subset sum problem is NP Complete. I was wondering if the following variation can be proved to be NP Complete : The cardinality of set of integers is $m$. And each element of the set is between $...
7
votes
2answers
749 views

Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?

I posted this on mathoverflow but with no luck: Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two ...
15
votes
1answer
358 views

Hitting set of pairwise intersecting families

A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$. The problem to find a minimum hitting ...
1
vote
1answer
199 views

Efficient verification of Kemeny-optimal rankings

The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\...
21
votes
1answer
894 views

For which k is PLANAR NAE k-SAT in P?

The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth ...
5
votes
3answers
663 views

Catalog of NP-complete problems, more up-to-date than Garey&Johnson?

Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&Johnson's book? I don't want to cite web sites, even though I ...
11
votes
1answer
523 views

What is the complexity of (possibly succinct) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number ...
5
votes
1answer
205 views

Enumeration of discrete objects for which recognition problem is coNP-complete

Is there any problem of enumeration of discrete objects for which problem of recognizing of these discrete objects is coNP-complete (or NP-complete), but it is possible to enumerate all these objects ...
23
votes
5answers
2k views

Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
0
votes
0answers
224 views

Does coNP-hardness imply NP-hardness [duplicate]

Possible Duplicate: Do many-one reductions and Turing reductions define the same class NPC Hi, Is the following true: If L is coNP-hard, then L is NP-hard. I have found statements of this, ...
12
votes
1answer
910 views

NP-hardness of a special case of Number Partitioning

Consider the following problem, Given a set of $n = k m$ positive numbers $\{ a_1, \dots, a_n \}$ in which $k \ge 3$ is a constant, we want to partition the set into $m$ subsets of size $k$ so that ...
22
votes
1answer
629 views

Does NP-hardness imply P-hardness?

If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)? It seems intuitive that if it is as hard as any problem in NP that it ...
66
votes
7answers
4k views

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space....
0
votes
1answer
753 views

graph coloring with 3 colors

I'm searching for an algorithm that can calculate a suboptimal solution for: color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the ...
15
votes
3answers
504 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...