User Andras Farago

11 votes

1 answer

221 views

Natural candidates for NP-E and E-NP

asked Jan 25, 2019 at 23:17

10 votes

2 answers

501 views

"Relatives" of the shortest path problem

asked Sep 12, 2019 at 23:40

10 votes

1 answer

758 views

Relationship between two graph optimization problems

asked Nov 18, 2019 at 4:32

10 votes

2 answers

235 views

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

asked Jul 29, 2015 at 14:40

10 votes

1 answer

283 views

Complexity of unique coloring of graphs

asked Apr 27, 2014 at 4:55

9 votes

1 answer

231 views

A curious asymmetry in good characterizations

asked Nov 6, 2014 at 0:50

9 votes

1 answer

515 views

Is the complexity of this path problem known?

asked Jan 29, 2015 at 17:42

9 votes

0 answers

363 views

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

asked Sep 19, 2016 at 3:30

8 votes

1 answer

330 views

Can a natural graph problem be universally hard?

asked Feb 11, 2014 at 17:12

7 votes

0 answers

637 views

Narrowing the gap between BPP and RP

asked Dec 4, 2012 at 15:54

7 votes

1 answer

176 views

Natural problem arising from diagonalization?

asked Feb 8, 2014 at 0:24

7 votes

2 answers

317 views

NPI-candidate hereditary graph property?

asked Mar 4, 2014 at 14:11

6 votes

1 answer

144 views

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

asked Mar 10, 2015 at 18:51

6 votes

1 answer

242 views

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

asked Feb 5, 2016 at 23:59

6 votes

1 answer

503 views

Complexity of finding the largest induced subgraph with all even degrees

asked Nov 18, 2019 at 20:23

5 votes

1 answer

188 views

Does p-isomorphism preserve phase transition?

asked Feb 28, 2016 at 14:18

5 votes

0 answers

217 views

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

asked Mar 22, 2016 at 4:05

5 votes

3 answers

511 views

Natural NP-complete problems with high density?

asked Nov 19, 2015 at 18:14

5 votes

1 answer

260 views

Minimum cost cut with discount - what is the complexity?

asked Apr 4, 2019 at 15:52

5 votes

0 answers

200 views

Question about a unary language construction

asked Aug 13, 2015 at 2:13

4 votes

0 answers

271 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?

asked Sep 5, 2014 at 22:31

4 votes

1 answer

188 views

Finding a "typical" path

asked Oct 22, 2022 at 5:11

3 votes

1 answer

124 views

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

asked Apr 6, 2018 at 23:52

3 votes

0 answers

208 views

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

asked Apr 2, 2015 at 15:57

3 votes

1 answer

996 views

Partitioning the edges of a complete graph into smaller complete graphs

asked May 25, 2015 at 2:43

2 votes

1 answer

300 views

Minimum Parity Weight Path - what is the complexity?

asked Feb 20, 2014 at 0:02

2 votes

1 answer

109 views

Natural relativized worlds

asked Dec 21, 2012 at 17:30

2 votes

0 answers

173 views

Best polynomial-time approximation factor for NP-optimization problems

asked Jan 5, 2019 at 16:54

2 votes

1 answer

74 views

Maximum subgraph problem with unknown complexity

asked Dec 17, 2019 at 4:57

1 vote

0 answers

60 views

Minimum rank graph cut

asked Feb 9, 2020 at 0:25

Stack Exchange Network

63 Questions

Natural candidates for NP-E and E-NP

"Relatives" of the shortest path problem

Relationship between two graph optimization problems

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

Complexity of unique coloring of graphs

A curious asymmetry in good characterizations

Is the complexity of this path problem known?

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

Can a natural graph problem be universally hard?

Narrowing the gap between BPP and RP

Natural problem arising from diagonalization?

NPI-candidate hereditary graph property?

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

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

Complexity of finding the largest induced subgraph with all even degrees

Does p-isomorphism preserve phase transition?

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

Natural NP-complete problems with high density?

Minimum cost cut with discount - what is the complexity?

Question about a unary language construction

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?

Finding a "typical" path

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

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

Partitioning the edges of a complete graph into smaller complete graphs

Minimum Parity Weight Path - what is the complexity?

Natural relativized worlds

Best polynomial-time approximation factor for NP-optimization problems

Maximum subgraph problem with unknown complexity

Minimum rank graph cut