Skip to main content
Share Your Experience: Take the 2024 Developer Survey
a3nm's user avatar
a3nm's user avatar
a3nm's user avatar
a3nm
  • Member for 13 years, 1 month
  • 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
799 views

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

23 votes
1 answer
986 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
556 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
421 views

Complexity of the homomorphism problem parameterized by treewidth

16 votes
1 answer
331 views

Which monotone Boolean functions are representable as thresholds on sums?

16 votes
4 answers
451 views

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

16 votes
2 answers
1k views

Complexity of counting the number of edge covers of a graph

16 votes
1 answer
355 views

What are bounded-treewidth circuits good for?

15 votes
3 answers
1k views

Complexity of topological sort with constrained positions

15 votes
1 answer
496 views

Imperfect subgraph isomorphism

14 votes
2 answers
364 views

Smallest set not included in a collection of sets

13 votes
1 answer
443 views

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

13 votes
2 answers
4k views

Lexicographically minimal topological sort of a labeled DAG

13 votes
0 answers
291 views

Which monotone DNFs are evasive?

13 votes
0 answers
217 views

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

13 votes
1 answer
275 views

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

12 votes
1 answer
2k views

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

12 votes
2 answers
1k views

Enumerating topological sorts of a vertex-labeled DAG

12 votes
0 answers
196 views

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

12 votes
2 answers
6k 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
289 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
521 views

Generalization of Dilworth's theorem for labeled DAGs

11 votes
1 answer
474 views

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

11 votes
2 answers
291 views

Is there a simple characterization of regular languages closed under circular shifts?

10 votes
1 answer
361 views

Lighting up all elements of a poset by toggling upsets