User a3nm

25 votes

1 answer

1k views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

asked Sep 11, 2015 at 13:53

25 votes

1 answer

792 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

asked May 21, 2015 at 17:28

23 votes

1 answer

952 views

Languages recognized by polynomial-size DFAs

asked May 5, 2014 at 12:49

23 votes

4 answers

6k views

Proof of the pumping lemma for context-free languages using pushdown automata

asked Jun 10, 2011 at 2:12

23 votes

2 answers

550 views

Testing whether letters can be scheduled to achieve a word in a regular language

asked Mar 1, 2018 at 13:43

18 votes

2 answers

2k views

"Almost sorting" integers in linear time

asked Apr 24, 2017 at 17:25

18 votes

0 answers

399 views

Complexity of the homomorphism problem parameterized by treewidth

asked Jun 2, 2016 at 10:37

16 votes

1 answer

321 views

Which monotone Boolean functions are representable as thresholds on sums?

asked May 12, 2015 at 22:57

16 votes

2 answers

1k views

Complexity of counting the number of edge covers of a graph

asked Feb 27, 2014 at 19:32

16 votes

1 answer

336 views

What are bounded-treewidth circuits good for?

asked Aug 28, 2014 at 12:52

15 votes

4 answers

442 views

Worst number of questions needed to learn a monotonic predicate over a poset

asked Jan 28, 2013 at 14:58

15 votes

3 answers

1k views

Complexity of topological sort with constrained positions

asked Sep 18, 2013 at 13:13

15 votes

1 answer

492 views

Imperfect subgraph isomorphism

asked May 30, 2012 at 22:03

14 votes

2 answers

362 views

Smallest set not included in a collection of sets

asked Dec 20, 2012 at 14:26

13 votes

2 answers

4k views

Lexicographically minimal topological sort of a labeled DAG

asked Jul 12, 2015 at 14:01

13 votes

0 answers

282 views

Which monotone DNFs are evasive?

asked Jul 16, 2019 at 20:28

12 votes

0 answers

191 views

Regular languages accepted by an automaton with at most one transition per letter

asked Nov 1, 2020 at 22:40

12 votes

1 answer

2k views

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

asked Nov 21, 2022 at 16:52

12 votes

1 answer

205 views

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

asked Sep 2 at 1:08

12 votes

2 answers

1k views

Enumerating topological sorts of a vertex-labeled DAG

asked Aug 4, 2016 at 12:36

12 votes

0 answers

175 views

Is it #P-hard to compute the number of antichains of a distributive lattice?

asked Nov 11, 2015 at 19:28

12 votes

1 answer

435 views

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

asked Dec 20, 2012 at 11:41

12 votes

2 answers

5k views

Space complexity to compute the optimal string alignment for the Levenshtein edit distance

asked Aug 31, 2012 at 15:39

11 votes

2 answers

387 views

Find items that are in at least $k$ of $n$ sets

asked Jul 3, 2012 at 13:10

11 votes

2 answers

279 views

Determining what can be achieved by a permutation of elements of a noncommutative group

asked Aug 23, 2015 at 19:00

11 votes

1 answer

1k views

Identifying useless edges for shortest path

asked Jun 17, 2014 at 21:03

11 votes

1 answer

475 views

Generalization of Dilworth's theorem for labeled DAGs

asked Nov 29, 2016 at 12:57

10 votes

0 answers

153 views

Which convex polytopes have volumes of polynomial bit-length?

asked Aug 18, 2016 at 23:45

10 votes

2 answers

361 views

Finding subgraphs with high treewidth and constant degree

asked Aug 28, 2017 at 21:33

10 votes

1 answer

359 views

Complexity of checking if two words have an interleaving in a language

asked Apr 3, 2017 at 14:49

Stack Exchange Network

71 Questions

Is it still open to determine the complexity of computing the treewidth of planar graphs?

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

Languages recognized by polynomial-size DFAs

Proof of the pumping lemma for context-free languages using pushdown automata

Testing whether letters can be scheduled to achieve a word in a regular language

"Almost sorting" integers in linear time

Complexity of the homomorphism problem parameterized by treewidth

Which monotone Boolean functions are representable as thresholds on sums?

Complexity of counting the number of edge covers of a graph

What are bounded-treewidth circuits good for?

Worst number of questions needed to learn a monotonic predicate over a poset

Complexity of topological sort with constrained positions

Imperfect subgraph isomorphism

Smallest set not included in a collection of sets

Lexicographically minimal topological sort of a labeled DAG

Which monotone DNFs are evasive?

Regular languages accepted by an automaton with at most one transition per letter

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

Enumerating topological sorts of a vertex-labeled DAG

Is it #P-hard to compute the number of antichains of a distributive lattice?

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

Space complexity to compute the optimal string alignment for the Levenshtein edit distance

Find items that are in at least $k$ of $n$ sets

Determining what can be achieved by a permutation of elements of a noncommutative group

Identifying useless edges for shortest path

Generalization of Dilworth's theorem for labeled DAGs

Which convex polytopes have volumes of polynomial bit-length?

Finding subgraphs with high treewidth and constant degree

Complexity of checking if two words have an interleaving in a language