Unanswered Questions
260 questions with no upvoted or accepted answers
11
votes
0
answers
240
views
Inapproximability of multiterminal cut
In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
CommunityBot
- 1
10
votes
0
answers
171
views
Is this problem on unambiguous DNFs hard?
Call a DNF formula $\varphi = \bigvee_{i=1}^n C_i$ unambiguous if for every $i\neq j$,
$C_i \land C_j$ is unsatisfiable. In other words, the disjunct $C_i$ contains some literal $l$ and $C_j$ contains ...
- 1,471
10
votes
0
answers
143
views
Reconstructing labeled poset from linear extensions
Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
CommunityBot
- 1
10
votes
0
answers
365
views
Gap hardness of Multi-Dimensional Cover
Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
CommunityBot
- 1
9
votes
0
answers
159
views
Optimal bee swarm plots: NP-hard?
Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with ...
- 56
9
votes
0
answers
401
views
Subset sum problem with at most one solution for any target
This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there.
We first consider the search version of the subset sum problem: Given a set $S$ of ...
- 23.2k
9
votes
0
answers
188
views
Complexity of fractional SAT
Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
- 2,742
9
votes
0
answers
264
views
Which version of KAKUTANI does lie in PPAD?
The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
- 546
9
votes
0
answers
1k
views
What are the best known reductions from SAT to CNF-SAT?
Problems
Let SAT denote the following problem:
Given a boolean formula, does there exist a satisfying assignment?
Let CNF-SAT denote the following problem:
Given a ...
- 5,167
9
votes
0
answers
361
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 (...
- 91
9
votes
0
answers
285
views
Advances towards proving the Held-Karp conjecture for TSP
I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.
The Held-Karp relaxation is conjectured to have an integrality gap of $\...
- 323
8
votes
0
answers
235
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 ...
- 14.5k
8
votes
0
answers
179
views
Is the dominating set problem constant-factor-approximable in undirected path graphs?
I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.
A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
- 21.8k
8
votes
0
answers
820
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 ...
CommunityBot
- 1
8
votes
0
answers
1k
views
Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?
This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal ...
CommunityBot
- 1