Skip to main content

Explore our questions

0 votes
0 answers
47 views
+50

Is set cover with a fixed number of variables and an arbitrary number of constraints fixed parameter tractable?

10 votes
2 answers
590 views

Determining if a word of specific length exists that is not accepted by a NFA

3 votes
0 answers
83 views

How to prove that a problem is not smoothed-polynomial?

1 vote
1 answer
115 views

Where does a problem lie which is NP-hard but not QMA-hard?

-2 votes
0 answers
52 views

Connect(G,k)={G is an undirected graph and uncomplete graph to wich you can add at most k edges to make it a clicque) is NP-Complete?

0 votes
0 answers
70 views

Minimize the dominating points

1 vote
0 answers
62 views

Is this kind of "multi-reduction" interesting?

2 votes
1 answer
107 views

Constrained Bipartite Matching

33 votes
5 answers
3k views

Is there a natural problem on the naturals that is NP-complete?

0 votes
0 answers
38 views

Bipartite Matching with a Partition Constraint over the Vertices

5 votes
3 answers
15k views

what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

13 votes
0 answers
628 views

Recent progress on the next-to-shortest-path problem for directed graphs?

0 votes
1 answer
83 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

0 votes
2 answers
92 views

strong NP-completeness of multi-dimensional Equal-Subset-Sum

Browse more Questions