Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
732
questions
3
votes
0
answers
104
views
Some questions about the Ryan O'Donnel and Yuan Zhou's paper "Approximability and proof complexity"
My question is particularly about the set-up in section $8$ (``Analysis of the KV Max-Cut instances") of the paper, https://arxiv.org/pdf/1211.1958.pdf.
What they call the Khot-Vishnoi UG instance ...
5
votes
1
answer
1k
views
Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?
It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ...
3
votes
0
answers
110
views
Can the Lasserre relaxation be defined over the reals?
If one wants to say minimize a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ on its domain then a degree$-d$ Lasserre relaxation of it would be to solve the problem of $\min \mathbb{E}_\mu [f(x)]$ ...
4
votes
1
answer
500
views
Proof that the graph optimization problem is NP-hard
I'm trying to prove that the following optimization problem is NP-hard:
Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
3
votes
0
answers
153
views
SOS and the small set expansion property
For what graphs do we know that their small set expansion property has a low degree SOS proof?
Is this known to be true for say the complete graphs?
A terminology issue about what is ``low degree" :...
30
votes
3
answers
1k
views
Did "Where the really hard problems are" hold up? What are current ideas on the subject?
I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually ...
2
votes
0
answers
74
views
Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?
Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, ...
7
votes
0
answers
245
views
How hard is PromiseFlowFree?
Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game:
The objective is to connect all pairs while covering the entire board, but in every puzzle there is always ...
1
vote
0
answers
35
views
How does one know what is not in a certain class of pseudo-distributions?
We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis.
Now say one has found a degree $...
15
votes
1
answer
472
views
Validity of exponentiation in a polynomial time reduction
I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.
In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-...
3
votes
0
answers
132
views
Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following ...
5
votes
1
answer
194
views
Finding a positive point for a collection of polynomials
I am wondering about the complexity of the following problem:
Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$,
$\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real ...
7
votes
0
answers
516
views
On the shortest vector problem (is it $NP$-complete?)
Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.
Has this been derandomized?
9
votes
1
answer
262
views
Consequences of a distillation algorithm for PSPACE
The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels".
Let a language $L$ be given. A distillation algorithm for $L$ takes a given
list of input ...
1
vote
0
answers
184
views
At what parameters is following $NP$-hard?
Problem Instances at given $\alpha>0$.
$(1)$ Given $a_1,\dots,a_{n^\alpha}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of that sums to $0$?
$(2)$ Given $a_1,\dots,a_{n}\in\Bbb Z$ ...
9
votes
0
answers
358
views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
2
votes
1
answer
175
views
Maximum stable matching/allocation
I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed ...
4
votes
1
answer
196
views
Is there any relationship of hardness between the two problems?
Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.
Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y ...
5
votes
0
answers
242
views
NP-completeness of a specific topological sorting problem
Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
8
votes
1
answer
464
views
complexity of a constraint satisfaction promise problem
(This is the "upper end" of my question from over 10 months ago on cs.stackexchange.
That question and the "lower end" I asked here over 8 months ago,
which I also have a bounty ...
4
votes
1
answer
115
views
From Lasserre maps to pseudo-distributions
Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
5
votes
2
answers
359
views
Hardness of $k$-Plex
Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of ...
1
vote
1
answer
1k
views
Positive 1-in-3 SAT FPT or Fixed Parameter Intractable
There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the ...
7
votes
1
answer
221
views
What are the hardness results known for CSP over $\mathbb{F}_q$?
I found two related papers,
There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf
A kind of a stronger result might be found in these two other papers, http://...
4
votes
2
answers
736
views
Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?
Consider the following problem:
Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
5
votes
1
answer
226
views
Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?
Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
-1
votes
1
answer
201
views
Given oracle for Max-3SAT compute clauses that cannot be satisfied
We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
-5
votes
2
answers
6k
views
Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?
Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
5
votes
2
answers
196
views
Solution/Hardness of the following (integer) budgeted problem?
I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!
Assume there are $N$ startups. For each startup $i$, you can invest $x_i\...
9
votes
1
answer
233
views
What is known about the hardness of the chromatic index for restricted graph classes?
There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them.
Are there any ...
6
votes
2
answers
261
views
Kth best problem that is NP-hard for K polynomial
A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to ...
3
votes
1
answer
142
views
What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]
We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also ...
8
votes
1
answer
335
views
NP-hardness on Cayley graphs
What is known about complexity of NP-hard problems on Cayley graphs?
Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
2
votes
1
answer
102
views
Constant Width Max Sum Product Multi-objective Shortest path problem
This question is a follow-up on the question I asked three days ago here.
For convenience I restate it here.
I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...
5
votes
1
answer
267
views
Max Sum Product Multi-objective Shortest path problem
Is anything known about the following problem:
I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1.
A path is first assigned a vector, ...
1
vote
0
answers
61
views
About increasing the objective values of certificates for Max-Clique SDP
Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
2
votes
0
answers
86
views
Max common sub forest on $k$ graphs
Not sure how to phrase this really, but here goes.
Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$.
The problem is to find ...
8
votes
0
answers
231
views
NP-hardness of approximation for unconstrained submodular maximization
The problem of unconstrained submodular maximization can be phrased as follows:
Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$.
Here a ...
3
votes
1
answer
567
views
What are some example problems for integer programming that are *not binary*
I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary.
Of course it is always possible ...
3
votes
1
answer
431
views
Variant of Subset Sum Problem with Changing Bound
Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that
$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$
$$...
2
votes
0
answers
97
views
About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
1
vote
0
answers
71
views
About complexity of recovering or learning Bayesian networks
Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
0
votes
1
answer
275
views
Packing sets to maximize overlap
For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.
Consider the following problem:
Input:
a list of $m$ weights $w = (w_1, \ldots, w_m)$,
a list of $n$ distinct subsets $T = (S_1, \ldots, ...
6
votes
3
answers
437
views
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Problem:
Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
7
votes
1
answer
1k
views
On reducing the hardness of CNF-SAT to k-Clique
CNF-SAT refers to the following problem:
Given a boolean formula $\phi$ in conjunctive normal form, does there
exist an assignment to the variables that satisfies $\phi$.
There are several ...
6
votes
1
answer
545
views
What is the complexity of vertex cover on k-partite graphs?
Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?
I guess that it's NP-hard, but couldn't yet prove it or find ...
4
votes
1
answer
362
views
Balanced Max-2-SAT NP-Hardness
The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ ...
1
vote
0
answers
191
views
Is "Binary Interval Tree" NP-hard? [closed]
The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which ...
3
votes
0
answers
221
views
Min dominating set software
I need a fast min-dominating-set code for some complexity lower bounds research I am doing.
I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something ...
17
votes
0
answers
945
views
Deeper look at Algorithmica?
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The ...