Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
713 questions
0
votes
0
answers
37
views
Is Exact Matching with more than two colours NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 353
5
votes
2
answers
641
views
Proof that NP is a subset of EXP
I would like to clarify a misunderstanding I have about the proof that all NP problems can be solved in exponential time. The argument as I understand it is that you can simply test all possible ...
- 319
1
vote
0
answers
45
views
Given a polygon P and a set of polygons S find the minimum number of polygons in S that covers P.
The union of the polygons you choose don't necessarily need to be equal exactly to the polygon P. I just need the minimum number of polygons in S that cover all of P so we may cover also a part beside ...
- 11
1
vote
0
answers
28
views
Complexity of deciding intersection arrays
Distance regular graphs can be described by their intersection arrays (https://en.wikipedia.org/wiki/Distance-regular_graph).
More precisely, an undirected graph of diameter d is distance-regular if ...
- 11
0
votes
1
answer
108
views
approximation algorithm for MAX-CLIQUE
Suppose we have given a 0.12 approximation algorithm for MAX-CLIQUE is an efficient algorithm that on an input graph G with optimal solution of size 𝑘, returns a clique of size at least 0.12⋅𝑘.
My ...
- 131
1
vote
0
answers
32
views
is there a Polynomial‑time reduction from k‑Dominating Set in arbitrary graphs to k‑Dominating Set in regular graphs?
I’m studying the complexity of the Dominating Set problem under degree constraints. It’s well known that deciding whether a graph
G has a dominating set of size
k is NP‑complete in general.
If such a ...
-2
votes
1
answer
95
views
Are specific cases of Boolean Satisfiability Problem cases, like 2 SAT still NP-complete?
Cook's theorem proves that all NP problems can be reduced to an NP-complete problem, SAT problem.
And we also know that specific subcategories of SAT problems like 2-SAT and Horn SAT can be solved in ...
0
votes
1
answer
62
views
HAM-CYCLE reduction to HAM-PATH?
I've been given the following question: Show that HAM-PATH $\propto$ HAM-CYCLE and, also, that HAM-CYCLE $\propto$ HAM-PATH.
I'm not confident on these types of questions but so far have this:
Given ...
- 135
0
votes
1
answer
110
views
how to prove that P=NP implies that there is a language in EXP that requires circuits of size $2^n/n$
This is a problem in Computational Complexity: A Modern Approach exercise 6.7, but I don't have any idea.
Here are some informations may be useful:
I know that P=NP implies that P=NP=PH
the hint in ...
0
votes
0
answers
33
views
Is the Unique Subset Partition Problem NP-complete?
From this paper
L. G. Valiant, V. V. Vazirani. “NP IS AS EASY AS DETECTING UNIQUE SOLUTIONS.” Theoretical Computer Science, 47 (1986) 85-93 North-Holland
is known that Unique SAT is NP-complete. ...
- 1,505
0
votes
0
answers
68
views
Proving that 2-clique problem is np-hard?
I have to prove that the 2-clique problem is np-hard, do I have to reduce it to the 2-independent set problem, or can I do it with the independent set alone? I know that if the graph G has 2 ...
- 11
0
votes
1
answer
82
views
Are there optimization problems in P?
I recently realized that the formal definitions of P and NP only include decision problems. However, I have often heard statements like “finding the shortest path in a graph is in P.”
Since P is ...
- 3
1
vote
1
answer
165
views
Tighter bound for Greedy Set Cover using Harmonic Sum
The Set Cover problem can be reformulated as
Given a collection $A_1, A_2, \ldots, A_m$ of subsets of a ground set $U$, and a positive integer $k$, please output a choice $K \subseteq \{ 1, 2, \ldots,...
- 1,856
0
votes
1
answer
76
views
Reducing ETP to GRAPH-k-COLORING
We are interested in scheduling n exams into k timeslots. Let $W_{nxn}$ be a symmetrical matrix where $W_{ij}$ gives the number of students that need to sit both exams i and j, where $W_{ij} = W_{ji}$....
- 135
0
votes
1
answer
39
views
How to show that MAX-CLIQUE transforms to MAX-IS?
I am doing a course in algorithms and heuristics, the main focus has been on graph theory and polynomial time problems, but now we have moved on to NP-Completeness and Polynomial-time transformations.
...
- 135