Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
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 ...
gradstudent's user avatar
  • 1,443
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 ...
xyz's user avatar
  • 243
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)]$ ...
gradstudent's user avatar
  • 1,443
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)...
marszall87's user avatar
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" :...
gradstudent's user avatar
  • 1,443
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 ...
dimpol's user avatar
  • 403
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, ...
gradstudent's user avatar
  • 1,443
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 ...
domotorp's user avatar
  • 13.9k
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 $...
gradstudent's user avatar
  • 1,443
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}$-...
Lamine's user avatar
  • 1,138
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 ...
Tanai's user avatar
  • 31
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 ...
Michael S.'s user avatar
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?
Turbo's user avatar
  • 12.8k
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 ...
Michael Wehar's user avatar
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$ ...
Turbo's user avatar
  • 12.8k
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 (...
pimlu's user avatar
  • 91
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 ...
user2789928's user avatar
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 ...
user2789928's user avatar
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 ...
Ivan Smirnov's user avatar
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 ...
user avatar
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 ...
gradstudent's user avatar
  • 1,443
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 ...
user avatar
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 ...
user1246462's user avatar
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://...
gradstudent's user avatar
  • 1,443
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, ...
Xing Zhou's user avatar
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 ...
Palash Dey's user avatar
-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 ...
user1246462's user avatar
-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 ...
TomR's user avatar
  • 409
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\...
user2789928's user avatar
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 ...
domotorp's user avatar
  • 13.9k
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 ...
xeqql's user avatar
  • 109
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 ...
domotorp's user avatar
  • 13.9k
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 ...
Igor Shinkar's user avatar
  • 1,927
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 ...
Nathanaël Fijalkow's user avatar
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, ...
Nathanaël Fijalkow's user avatar
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 ...
Student's user avatar
  • 654
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 ...
user1441057's user avatar
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 ...
Yuval Filmus's user avatar
  • 14.4k
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 ...
Lagerbaer's user avatar
  • 329
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$$ $$...
Tomlin's user avatar
  • 41
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$...
Student's user avatar
  • 654
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 ...
Student's user avatar
  • 654
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, ...
Christos AMS's user avatar
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 ...
Phylliida's user avatar
  • 1,132
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 ...
Michael Wehar's user avatar
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 ...
eleKtronaj's user avatar
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$ ...
Manuel Lafond's user avatar
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 ...
Esantin's user avatar
  • 11
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 ...
Chad Brewbaker's user avatar
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 ...
András Salamon's user avatar

1
5 6
7
8 9
15