a3nm's user avatar
a3nm's user avatar
a3nm's user avatar
a3nm
  • Member for 12 years, 5 months
  • Last seen this week
  • Télécom Paris, greater Paris
25 votes
1 answer
1k views

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

25 votes
1 answer
792 views

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

23 votes
1 answer
952 views

Languages recognized by polynomial-size DFAs

23 votes
4 answers
6k views

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

23 votes
2 answers
550 views

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

18 votes
2 answers
2k views

"Almost sorting" integers in linear time

18 votes
0 answers
399 views

Complexity of the homomorphism problem parameterized by treewidth

16 votes
1 answer
321 views

Which monotone Boolean functions are representable as thresholds on sums?

16 votes
2 answers
1k views

Complexity of counting the number of edge covers of a graph

16 votes
1 answer
336 views

What are bounded-treewidth circuits good for?

15 votes
4 answers
442 views

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

15 votes
3 answers
1k views

Complexity of topological sort with constrained positions

15 votes
1 answer
492 views

Imperfect subgraph isomorphism

14 votes
2 answers
362 views

Smallest set not included in a collection of sets

13 votes
2 answers
4k views

Lexicographically minimal topological sort of a labeled DAG

13 votes
0 answers
282 views

Which monotone DNFs are evasive?

12 votes
0 answers
191 views

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

12 votes
1 answer
2k views

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

12 votes
1 answer
205 views

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

12 votes
2 answers
1k views

Enumerating topological sorts of a vertex-labeled DAG

12 votes
0 answers
175 views

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

12 votes
1 answer
435 views

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

12 votes
2 answers
5k views

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

11 votes
2 answers
387 views

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

11 votes
2 answers
279 views

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

11 votes
1 answer
1k views

Identifying useless edges for shortest path

11 votes
1 answer
475 views

Generalization of Dilworth's theorem for labeled DAGs

10 votes
0 answers
153 views

Which convex polytopes have volumes of polynomial bit-length?

10 votes
2 answers
361 views

Finding subgraphs with high treewidth and constant degree

10 votes
1 answer
359 views

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