Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

3
votes
0answers
86 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
1answer
606 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 ...
4
votes
0answers
103 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)]$ ...
5
votes
1answer
376 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)...
4
votes
0answers
107 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" :...
27
votes
3answers
853 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
0answers
62 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, ...
8
votes
0answers
210 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
0answers
27 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 $...
16
votes
1answer
407 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}$-...
4
votes
0answers
123 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 ...
6
votes
1answer
188 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 ...
6
votes
0answers
259 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
1answer
224 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
0answers
181 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$ ...
10
votes
0answers
299 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
1answer
145 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 ...
5
votes
1answer
187 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 ...
4
votes
0answers
163 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
1answer
369 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 on, are both ...
4
votes
1answer
95 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
2answers
202 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
1answer
518 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
1answer
150 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://...
3
votes
2answers
390 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
1answer
160 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
1answer
122 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
2answers
1k 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 ...
6
votes
2answers
187 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
1answer
187 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 ...
7
votes
2answers
223 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
1answer
93 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 ...
9
votes
1answer
242 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
1answer
72 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
1answer
151 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
0answers
50 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
0answers
84 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 ...
9
votes
0answers
160 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 ...
2
votes
1answer
277 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
1answer
244 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
0answers
90 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$...
0
votes
0answers
59 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 ...
1
vote
1answer
209 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, ...
4
votes
2answers
169 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
1answer
517 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 ...
7
votes
1answer
361 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 ...
5
votes
1answer
190 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
0answers
159 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
0answers
173 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
0answers
635 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 ...