The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
3
votes
1answer
581 views

Simplest proof of NP-completeness

The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many ...
6
votes
1answer
220 views

NP-completeness of a problem using a “T-gadget”

Working on a problem I came up with the following "T-gadget": It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2); it can be rotated (0, 90, 180, 270 degrees); two ...
13
votes
3answers
499 views

Is this optimum travelling problem under deadlines NP-hard on trees?

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it? Problem: There is a tree $T(V,E)$, each edge has symmetric ...
3
votes
1answer
300 views

reduction of maximum independet set to minimum distance of code

Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
-1
votes
2answers
757 views

What progress has been made to prove whether or not p=np? [closed]

I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this ...
18
votes
4answers
2k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
3
votes
1answer
393 views

Approximate bound/algorithm for “product of sums maximization” problem

I am looking for some approximate algorithm with upper/lower bound for the following problem: Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint ...
27
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
231 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
684 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
396 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
745 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
276 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
907 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
356 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
241 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
736 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
673 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
363 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
342 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
920 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
715 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
529 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
465 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. ...
55
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
237 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
753 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
360 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
202 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\...
23
votes
1answer
914 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
668 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
532 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 ...