User a3nm

25 votes

1 answer

883 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

772 views

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

cc.complexity-theory co.combinatorics np-hardness permutations

asked May 21, 2015 at 17:28

23 votes

1 answer

824 views

Languages recognized by polynomial-size DFAs

reference-request fl.formal-languages automata-theory online-algorithms dfa

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

fl.formal-languages automata-theory proofs grammars

asked Jun 10, 2011 at 2:12

23 votes

2 answers

538 views

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

cc.complexity-theory np-hardness automata-theory regular-language scheduling

asked Mar 1, 2018 at 13:43

18 votes

2 answers

2k views

"Almost sorting" integers in linear time

reference-request time-complexity sorting

asked Apr 24, 2017 at 17:25

16 votes

1 answer

285 views

Which monotone Boolean functions are representable as thresholds on sums?

reference-request boolean-functions

asked May 12, 2015 at 22:57

16 votes

0 answers

352 views

Complexity of the homomorphism problem parameterized by treewidth

graph-algorithms parameterized-complexity treewidth fixed-parameter-tractable homomorphism

asked Jun 2, 2016 at 10:37

16 votes

2 answers

948 views

Complexity of counting the number of edge covers of a graph

reference-request graph-algorithms counting-complexity proofs

asked Feb 27, 2014 at 19:32

16 votes

1 answer

308 views

What are bounded-treewidth circuits good for?

circuit-complexity pr.probability treewidth arithmetic-circuits

asked Aug 28, 2014 at 12:52

15 votes

4 answers

423 views

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

ds.algorithms lg.learning partial-order search-problem order-theory

asked Jan 28, 2013 at 14:58

15 votes

3 answers

1k views

Complexity of topological sort with constrained positions

sorting directed-acyclic-graph partial-order order-theory topological-sorting

asked Sep 18, 2013 at 13:13

15 votes

1 answer

482 views

Imperfect subgraph isomorphism

cc.complexity-theory ds.algorithms graph-theory approximation-algorithms graph-isomorphism

asked May 30, 2012 at 22:03

14 votes

2 answers

355 views

Smallest set not included in a collection of sets

cc.complexity-theory ds.algorithms

asked Dec 20, 2012 at 14:26

13 votes

2 answers

4k views

Lexicographically minimal topological sort of a labeled DAG

cc.complexity-theory np-hardness directed-acyclic-graph order-theory topological-sorting

asked Jul 12, 2015 at 14:01

13 votes

0 answers

252 views

Which monotone DNFs are evasive?

np-hardness boolean-functions

asked Jul 16, 2019 at 20:28

12 votes

0 answers

180 views

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

reference-request fl.formal-languages automata-theory regular-language

asked Nov 1, 2020 at 22:40

12 votes

2 answers

1k views

Enumerating topological sorts of a vertex-labeled DAG

cc.complexity-theory sorting directed-acyclic-graph partial-order topological-sorting

asked Aug 4, 2016 at 12:36

12 votes

0 answers

158 views

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

reference-request counting-complexity partial-order lattice

asked Nov 11, 2015 at 19:28

12 votes

1 answer

408 views

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

ds.algorithms ds.data-structures partial-order order-theory search-problem

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

cc.complexity-theory dynamic-algorithms edit-distance space-time-tradeoff

asked Aug 31, 2012 at 15:39

11 votes

2 answers

386 views

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

ds.algorithms

asked Jul 3, 2012 at 13:10

11 votes

2 answers

274 views

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

np-hardness sorting gr.group-theory partial-order order-theory

asked Aug 23, 2015 at 19:00

11 votes

1 answer

1k views

Identifying useless edges for shortest path

ds.algorithms reference-request graph-algorithms shortest-path

asked Jun 17, 2014 at 21:03

11 votes

1 answer

405 views

Generalization of Dilworth's theorem for labeled DAGs

reference-request graph-theory directed-acyclic-graph partial-order

asked Nov 29, 2016 at 12:57

10 votes

0 answers

145 views

Which convex polytopes have volumes of polynomial bit-length?

reference-request computational-geometry convex-geometry polytope

asked Aug 18, 2016 at 23:45

10 votes

2 answers

329 views

Finding subgraphs with high treewidth and constant degree

co.combinatorics treewidth graph-minor bounded-degree

asked Aug 28, 2017 at 21:33

10 votes

1 answer

348 views

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

cc.complexity-theory reference-request regular-language

asked Apr 3, 2017 at 14:49

10 votes

1 answer

317 views

Lighting up all elements of a poset by toggling upsets

graph-theory boolean-functions directed-acyclic-graph partial-order order-theory

asked Oct 12, 2019 at 11:35

10 votes

0 answers

129 views

Reconstructing labeled poset from linear extensions

cc.complexity-theory ds.algorithms np-hardness partial-order order-theory

asked Nov 24, 2014 at 19:11

Stack Exchange Network

current community

your communities

more stack exchange communities

60 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

Which monotone Boolean functions are representable as thresholds on sums?

Complexity of the homomorphism problem parameterized by treewidth

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

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

Lighting up all elements of a poset by toggling upsets

Reconstructing labeled poset from linear extensions