User Thinh D. Nguyen

6 votes

1 answer

369 views

Path in an edge-weighted undirected graph

asked Aug 12, 2018 at 11:12

5 votes

2 answers

2k views

NP-completeness of Induced disjoint paths

asked May 28, 2019 at 4:42

4 votes

2 answers

123 views

Karp hardness of searching for a matching cut

asked Sep 7, 2018 at 5:34

4 votes

1 answer

160 views

Vertex cover with covering radius 2

asked Sep 15, 2018 at 6:23

3 votes

1 answer

44 views

Karp hardness of searching for a matching erosion

asked Sep 9, 2018 at 4:26

3 votes

1 answer

86 views

Karp hardness of searching for a matching split

asked Sep 10, 2018 at 4:43

3 votes

0 answers

51 views

Karp hardness of a module in a graph

asked Oct 5, 2018 at 12:49

2 votes

0 answers

265 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

asked Jun 1, 2019 at 9:57

2 votes

0 answers

28 views

Karp hardness of two vertex sets in a digraph

asked Jan 12, 2019 at 5:50

2 votes

1 answer

79 views

Karp hardness of an equidistant vertex set

asked Sep 22, 2018 at 7:49

2 votes

1 answer

138 views

Path in a vertex-weighted undirected graph

asked Aug 12, 2018 at 6:37

1 vote

1 answer

200 views

Ordering the incident edges of each vertex to have a specified pre-order traversal

asked Jul 14, 2018 at 8:28

1 vote

0 answers

42 views

A HUGE GAP in time: Complete problem for $\mathrm{strict}$-$\mathrm{SUBEXP}$

asked Sep 3, 2018 at 16:45

1 vote

0 answers

44 views

Karp hardness of a simply equidistant vertex set

asked Sep 23, 2018 at 8:02

1 vote

2 answers

64 views

Karp hardness of digraph coloring without monochromatic dicycle

asked Sep 28, 2018 at 10:29

1 vote

1 answer

46 views

Karp hardness of a guarding set in digraph

asked Sep 29, 2018 at 8:18

1 vote

1 answer

42 views

Karp hardness of a vector system allocation

asked Sep 30, 2018 at 11:34

1 vote

2 answers

93 views

Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

asked Oct 1, 2018 at 6:44

1 vote

1 answer

171 views

Karp hardness of directed monochromatic triangle problem

asked Oct 20, 2018 at 6:56

1 vote

0 answers

38 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

asked Dec 28, 2018 at 5:01

1 vote

1 answer

173 views

Non-constructive $NP$-completeness proof

asked Oct 11, 2018 at 9:15

1 vote

1 answer

51 views

Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

asked Oct 17, 2018 at 4:37

0 votes

1 answer

36 views

Robustness of non-context-free proof against trivial manipulation

asked Oct 18, 2018 at 6:23

0 votes

1 answer

39 views

Karp hardness of a diameter-decreasing planted clique

asked Oct 12, 2018 at 8:00

0 votes

1 answer

55 views

Karp hardness of a clique with given number of outer-incident edges

asked Oct 7, 2018 at 8:45

0 votes

1 answer

78 views

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

asked Nov 27, 2018 at 1:43

0 votes

1 answer

44 views

Karp hardness of an equidistant set in digraph

asked Sep 25, 2018 at 10:26

0 votes

1 answer

34 views

Weakest reduction for 3-$\mathrm{SAT}$

asked Sep 1, 2018 at 7:01

0 votes

1 answer

44 views

Cook completeness of a variant of Vertex Cover

asked Aug 27, 2018 at 7:59

0 votes

3 answers

65 views

Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

asked Aug 29, 2018 at 2:10

Stack Exchange Network

33 Questions

Path in an edge-weighted undirected graph

NP-completeness of Induced disjoint paths

Karp hardness of searching for a matching cut

Vertex cover with covering radius 2

Karp hardness of searching for a matching erosion

Karp hardness of searching for a matching split

Karp hardness of a module in a graph

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

Karp hardness of two vertex sets in a digraph

Karp hardness of an equidistant vertex set

Path in a vertex-weighted undirected graph

Ordering the incident edges of each vertex to have a specified pre-order traversal

A HUGE GAP in time: Complete problem for $\mathrm{strict}$-$\mathrm{SUBEXP}$

Karp hardness of a simply equidistant vertex set

Karp hardness of digraph coloring without monochromatic dicycle

Karp hardness of a guarding set in digraph

Karp hardness of a vector system allocation

Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

Karp hardness of directed monochromatic triangle problem

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Non-constructive $NP$-completeness proof

Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

Robustness of non-context-free proof against trivial manipulation

Karp hardness of a diameter-decreasing planted clique

Karp hardness of a clique with given number of outer-incident edges

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

Karp hardness of an equidistant set in digraph

Weakest reduction for 3-$\mathrm{SAT}$

Cook completeness of a variant of Vertex Cover

Collection of meta-reductions in theory of $\mathrm{NP}$-completeness