User a3nm

12

25

votes

1

answer

758

views

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

Jun 18 '15 at 9:43 Community♦ 1

8

24

votes

1

answer

803

views

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

reference-request graph-theory np-hardness open-problem treewidth

Sep 11 '15 at 22:31 Community♦ 1

4

23

votes

2

answers

527

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

Mar 4 '18 at 21:29 a3nm 6,995

8

23

votes

1

answer

709

views

Languages recognized by polynomial-size DFAs

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

Jun 18 '15 at 10:16 a3nm 6,995

9

21

votes

4

answers

6k

views

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

fl.formal-languages automata-theory proofs grammars

Jan 20 '18 at 13:55 Lamine 1,074

4

16

votes

2

answers

860

views

Complexity of counting the number of edge covers of a graph

reference-request graph-algorithms counting-complexity proofs

Aug 28 '19 at 11:54 a3nm 6,995

2

16

votes

2

answers

2k

views

“Almost sorting” integers in linear time

reference-request time-complexity sorting

Jun 15 '19 at 12:37 David 188

3

16

votes

1

answer

247

views

Which monotone Boolean functions are representable as thresholds on sums?

reference-request boolean-functions

Sep 1 '18 at 23:41 Bjørn Kjos-Hanssen♦ 4,308

4

16

votes

0

answers

325

views

Complexity of the homomorphism problem parameterized by treewidth

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

Jun 2 '16 at 10:37 a3nm 6,995

4

15

votes

3

answers

975

views

Complexity of topological sort with constrained positions

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

May 15 '20 at 15:49 a3nm 6,995

2

15

votes

1

answer

283

views

What are bounded-treewidth circuits good for?

circuit-complexity pr.probability treewidth arithmetic-circuits

Oct 29 '18 at 16:40 a3nm 6,995

1

15

votes

4

answers

408

views

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

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

Feb 7 '13 at 12:01 Community♦ 1

4

15

votes

1

answer

478

views

Imperfect subgraph isomorphism

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

Nov 11 '12 at 5:59 Community♦ 1

14

votes

2

answers

355

views

Smallest set not included in a collection of sets

cc.complexity-theory ds.algorithms

Dec 20 '12 at 15:53 Yury 3,751

1

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

May 15 '20 at 15:50 a3nm 6,995

2

13

votes

0

answers

228

views

Which monotone DNFs are evasive?

np-hardness boolean-functions

Jul 17 '19 at 14:06 a3nm 6,995

1

12

votes

2

answers

849

views

Enumerating topological sorts of a vertex-labeled DAG

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

Apr 2 at 19:59 Gregory Morse 9

2

12

votes

0

answers

168

views

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

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

Nov 2 at 10:45 a3nm 6,995

12

votes

0

answers

147

views

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

reference-request counting-complexity partial-order lattice

Nov 11 '15 at 19:28 a3nm 6,995

1

12

votes

1

answer

377

views

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

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

Feb 7 '13 at 9:31 Community♦ 1

3

12

votes

2

answers

4k

views

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

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

Sep 1 '12 at 15:08 Jeffε 22.6k

11

votes

2

answers

269

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

May 11 '18 at 12:32 a3nm 6,995

1

11

votes

1

answer

371

views

Generalization of Dilworth's theorem for labeled DAGs

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

May 9 '18 at 6:24 a3nm 6,995

2

11

votes

1

answer

959

views

Identifying useless edges for shortest path

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

Jun 23 '14 at 22:37 JimN 1,227

3

11

votes

2

answers

386

views

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

ds.algorithms

Jul 11 '12 at 12:19 Massimo Cafaro 2,176

4

10

votes

1

answer

283

views

Lighting up all elements of a poset by toggling upsets

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

May 3 '20 at 11:27 a3nm 6,995

10

votes

1

answer

306

views

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

cc.complexity-theory reference-request regular-language

Apr 3 '17 at 17:18 Community♦ 1

1

10

votes

0

answers

141

views

Which convex polytopes have volumes of polynomial bit-length?

reference-request computational-geometry convex-geometry polytope

Aug 20 '16 at 3:56 domotorp 13.2k

10

votes

0

answers

127

views

Reconstructing labeled poset from linear extensions

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

May 21 '15 at 17:31 Community♦ 1

3

10

votes

1

answer

4k

views

Monotone bijections between lists of intervals

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

Jul 8 '14 at 16:11 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

59 Questions

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

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

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

Languages recognized by polynomial-size DFAs

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

Complexity of counting the number of edge covers of a graph

“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 topological sort with constrained positions

What are bounded-treewidth circuits good for?

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

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?

Enumerating topological sorts of a vertex-labeled DAG

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

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

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

Generalization of Dilworth's theorem for labeled DAGs

Identifying useless edges for shortest path

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

Lighting up all elements of a poset by toggling upsets

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

Which convex polytopes have volumes of polynomial bit-length?

Reconstructing labeled poset from linear extensions

Monotone bijections between lists of intervals