Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 4 months
  • Last seen more than a month ago
11 votes
1 answer
220 views

Natural candidates for NP-E and E-NP

10 votes
2 answers
488 views

"Relatives" of the shortest path problem

10 votes
1 answer
758 views

Relationship between two graph optimization problems

10 votes
2 answers
234 views

Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

10 votes
1 answer
283 views

Complexity of unique coloring of graphs

9 votes
1 answer
231 views

A curious asymmetry in good characterizations

9 votes
1 answer
514 views

Is the complexity of this path problem known?

9 votes
0 answers
361 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

8 votes
1 answer
329 views

Can a natural graph problem be universally hard?

7 votes
0 answers
637 views

Narrowing the gap between BPP and RP

7 votes
1 answer
175 views

Natural problem arising from diagonalization?

7 votes
2 answers
317 views

NPI-candidate hereditary graph property?

6 votes
1 answer
142 views

Maximum number of geometrically disjoint paths - is the complexity known?

6 votes
1 answer
242 views

Graph class with easy chromatic number, but NP-hard coloring

6 votes
1 answer
481 views

Complexity of finding the largest induced subgraph with all even degrees

5 votes
1 answer
187 views

Does p-isomorphism preserve phase transition?

5 votes
0 answers
209 views

When will an NP-complete language remain hard if half of a witness is revealed with the instance?

5 votes
3 answers
505 views

Natural NP-complete problems with high density?

5 votes
1 answer
253 views

Minimum cost cut with discount - what is the complexity?

5 votes
0 answers
199 views

Question about a unary language construction

4 votes
0 answers
268 views

Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

4 votes
1 answer
185 views

Finding a "typical" path

3 votes
1 answer
124 views

Results/concepts that also proved useful outside of their "home areas"

3 votes
0 answers
201 views

Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

3 votes
1 answer
960 views

Partitioning the edges of a complete graph into smaller complete graphs

2 votes
1 answer
298 views

Minimum Parity Weight Path - what is the complexity?

2 votes
1 answer
106 views

Natural relativized worlds

2 votes
0 answers
172 views

Best polynomial-time approximation factor for NP-optimization problems

2 votes
1 answer
74 views

Maximum subgraph problem with unknown complexity

1 vote
0 answers
57 views

Minimum rank graph cut