Skip to main content
R B's user avatar
R B's user avatar
R B's user avatar
R B
  • Member for 10 years, 5 months
  • Last seen more than a month ago
23 votes
Accepted

Is NP in $DTIME(n^{poly\log n})$?

16 votes

Hardest known natural problem in P?

13 votes
Accepted

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

12 votes
Accepted

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

11 votes
Accepted

Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs?

11 votes

Regular languages under change of encoding

11 votes

What notable automaton models have polynomially-decidable containment?

10 votes

Graph coloring minimizing the number of colors in every independent set

10 votes
Accepted

Easy decision hard counting Parametrized

10 votes

Examples where the uniqueness of the solution makes it easier to find

9 votes

Shortest path hitting a given vertex

9 votes
Accepted

Max flow: either saturate an edge or avoids

9 votes
Accepted

Is optimal equal-point graph splitting NP-Complete?

9 votes

Lower-bound of a decision problem

8 votes

Intuition: Odd-cycle transversal in triangle-free graphs

8 votes

Streaming algorithms suitable for undergrad course

7 votes
Accepted

Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

7 votes
Accepted

What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

7 votes
Accepted

Tight examples for approximating the feedback vertex set problem

7 votes

Counting the Number of Simple Paths in Undirected Graph

7 votes

Problems that are easy on unweighted graphs, but hard for weighted graphs

6 votes
Accepted

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

6 votes
Accepted

Shortest distance/path between two households

6 votes

Complexity of solving linear equations

6 votes
Accepted

Finding the minimum number of coordinates to change to get a vector inside a subspace

5 votes

Variation on partial Set Cover with penalties

5 votes
Accepted

Is the following problem in P or in NP?

5 votes
Accepted

Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

5 votes

Greedy MAX SAT approximation ratio

4 votes

Transitivity check vs. Transitive Closure