decision problems that are at least as hard as NP-complete problems
-1
votes
0answers
4 views
0
votes
0answers
7 views
Karp hardness of a supportive clique in digraphs
In a directed graph (digraph) $G(V,A)$, a set of vertices $C\subseteq V$ is called a supportive clique if (1) for every $u\neq v$ in $C$, either $(u,v)\in A$ or $(v,u)\in A$ and (2) for every $u\in C$,...
1
vote
1answer
15 views
Karp hardness of a diameter-decreasing planted clique
A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}...
2
votes
0answers
32 views
Non-constructive $NP$-completeness proof
Is there any known $NP$-complete problem which hardness proof is non-constructive.
A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument ...
1
vote
1answer
43 views
For each given set choosing either it or its complement such that their union exactly has a given size
Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
1
vote
1answer
43 views
Karp hardness of a clique with given number of outer-incident edges
A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$.
Given a clique $\mathcal{C}\subseteq ...
4
votes
0answers
37 views
Karp hardness of a module in a graph
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:
For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
0
votes
1answer
32 views
On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem
in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.
Besides, it's easy to ...
2
votes
2answers
63 views
Karp hardness of testing for homomorphisms to a fixed non-bipartite graph
Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$...
2
votes
1answer
35 views
Karp hardness of a vector system allocation
Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
2
votes
1answer
24 views
Karp hardness of a guarding set in digraph
Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.
A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
2
votes
2answers
39 views
Karp hardness of digraph coloring without monochromatic dicycle
Problem statement:
Input: a digraph $G(V, A)$ and a natural number $k$
Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, ...
1
vote
1answer
35 views
Karp hardness of an equidistant set in digraph
Following the success of the undirected version:
Karp hardness of an equidistant vertex set
Inspired by the success of this long ago question:
NP-hardness of problem with indices and subsets
We ...
2
votes
0answers
35 views
Karp hardness of a simply equidistant vertex set
Following the success of the previous question:
Karp hardness of an equidistant vertex set
I continue to propse yet another computational problem. This time, we modify the notion of an equidistant ...
3
votes
1answer
59 views
Karp hardness of an equidistant vertex set
What is the hardness of the following problem?
Input: An undirected graph $G(V, E)$ and a natural number $k$
Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO
$\...
1
vote
1answer
22 views
Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?
Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
0
votes
0answers
61 views
Is the following problem generalizing X3C?
The first problem is X3C for which I try to find out whether it's a special case of the second problem.
The second one is a stacking problem for which we have an itemset $I := \{i_1, ..., i_n\}$, $m$ ...
4
votes
0answers
27 views
Finding the “most modular” subset of graph vertices, i.e. that minimize disagreement inside and outside
Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
1
vote
0answers
21 views
Edge-midpoints cover with radius 1
This is in a series of posts. Previous quetion:
Vertex cover with covering radius 2
Other series: Karp hardness of searching for a matching split
In this problem, our cover for a given undirected ...
6
votes
1answer
45 views
Vertex cover with covering radius 2
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?
A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
4
votes
1answer
65 views
Karp hardness of searching for a matching split
UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
3
votes
1answer
63 views
Maximum induced tree
Given an undirected graph $G(V, E)$, how hard is it to decide whether it has an induced tree consisting of $k$ vertices, where $k$ is also given in the input?
4
votes
1answer
33 views
Karp hardness of searching for a matching erosion
First, read the previous question: Karp hardness of searching for a matching cut
As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
1
vote
3answers
73 views
Defining a graph decision problem not in NP
I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the ...
6
votes
2answers
82 views
Karp hardness of searching for a matching cut
Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split
Maximum Matching Cut problem
Input: An undirected graph $G(...
3
votes
1answer
20 views
Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
-3
votes
2answers
111 views
Does deep learning infer P = NP?
The question comes from the following scenario,
assume we have the traveler problem which is NP (the one where a traveler wants to visit all countries with the lowest cost(by summing up all flights))
...
1
vote
3answers
20 views
Collection of meta-reductions in theory of $\mathrm{NP}$-completeness
I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness.
This can be regarded as a reference request post. Any links are appreciated.
At least, ...
1
vote
1answer
26 views
Cook completeness of a variant of Vertex Cover
Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?
Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$
Output: YES if there exists a vertex cover $C'\...
4
votes
1answer
58 views
Ordered set cover problem: is it NP-hard?
Given a set of elements $U=\{1,2,\ldots,n\}$ and a collection of $m$ sets $\{S_1,S_2,\ldots,S_m\}$ whose union equals $U$. Each element $e$ of a set $S_i$ has a weight $w_i(e)$. The weight $w(S_i)$ of ...
2
votes
2answers
112 views
Is this problem NP-hard? Maximizing selected sets so that their union is less than k?
There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union.
I'm currently ...
1
vote
1answer
22 views
Optimal combination, given pairwise costs
I want to pick k objects from a pool of n. Not any k objects, the optimal k objects: that which minimizes the cost of the set, defined as the sum of pairwise costs for all pairs within the set.
What ...
6
votes
2answers
132 views
Does there exist a travelling salesmen generating algorithm?
I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling ...
4
votes
1answer
133 views
Is this scheduling problem with arrival times, deadlines, and costs NP-hard?
There are $n$ jobs where each job $i$ has an arrival time $r_i$, a deadline $d_i$ and a cost $c_i$. The problem is to find a scheduling time $t_i$ (where $r_i\leq t_i\leq d_i$) for each job $i$ in ...
-1
votes
1answer
27 views
Finding a Hamilton path in a Complete Euclidean Graph is in P
How is it possible to prove that this assert is not true?
2
votes
0answers
38 views
Finding maximum weighted n disjoint cliques
Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations?
Given a ...
2
votes
1answer
60 views
“Fuzzy” Chinese Remainder Theorem NP-hard?
I have some "fuzzy" congruences like these:
\begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \...
4
votes
2answers
58 views
Largest weight-limited connected subgraph: NP-complete?
When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of ...
1
vote
1answer
64 views
Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
2
votes
1answer
50 views
Careful 5COLOR NP hardness
Given the following definition of Careful 5COLORING:
A 5-coloring is careful if the colors assigned to adjacent vertices
are not only distinct, but differ by more than 1(mod 5)
how would a ...
4
votes
1answer
41 views
Decomposing NP-hard sets
Suppose A∪B is NP-hard, does it follow that A is NP-hard or B is NP-hard?
Equivalently, is the property "not NP-hard" closed under union?
A related question was already asked:
Are NP-complete sets ...
2
votes
1answer
45 views
Prove np-hardness of dividing items from the lists
I have a problem:
There is finished number of lists of items. The same item can be on many lists. I would like to color items (there are 3 available colors) that on every list there are items in at ...
0
votes
0answers
32 views
Vertex which is present in all Minimum Dominating Sets for Bipartite graphs
I am working on Minimum Dominating sets for bipartite graphs. There can be many minimum dominating sets of same size and I want vertex which is present in all of them. My approach for generating ...
0
votes
0answers
20 views
Determining epsilon for knapsack problem solved with FPTAS
I want to solve the knapsack problem with FPTAS and two parameters $\varepsilon_1 <\varepsilon_2$ .
I know that as long as we choose smaller epsilon we get more tight approximation but we pay with ...
3
votes
1answer
46 views
A TSP to HamCycle Reduction
I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...
1
vote
2answers
175 views
Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?
The following problem is from my algorithms class:
Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph ...
2
votes
1answer
104 views
Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?
The following problem is from my algorithms class:
Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $...
1
vote
2answers
85 views
Is it NP complete to decide whether a graph has $k$ disjoint triangles?
I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$
but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in ...
0
votes
1answer
45 views
Is this language NP Hard?
$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}...
0
votes
0answers
10 views
Explain NP-Hard using an example [duplicate]
I can't grasp the concept of NP-Hard. Basically I have come accross two definitions, summarizing them this is what I understand:
Applies the oncept of reducability - Transform problem A to another S, ...
