Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

0 votes
0 answers
10 views

Dual of cut of embedded graph disconnects surface

12 votes
4 answers
4k views

Incremental Maximum Flow in Dynamic graphs

8 votes
1 answer
188 views

Monotone circuit representations of paths in a graph?

-1 votes
0 answers
25 views

How to write a simulation to monte-carlo estimate the "probability that such a random coloring on $G$ is successful"

13 votes
4 answers
4k views

The number of cliques in a graph: the Moon and Moser 1965 result

3 votes
0 answers
82 views

Approximative counting of matchings in a graph

-1 votes
1 answer
50 views

Unweighted bipartite $b$-Matching

1 vote
0 answers
42 views

Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?

2 votes
1 answer
75 views

Regularity Lemma for Multi-Relational Graphs?

2 votes
0 answers
74 views

Finding Hamilton cycles in random graphs

10 votes
2 answers
343 views

Complexity of digraph homomorphism to an oriented cycle

0 votes
1 answer
78 views

Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

1 vote
0 answers
50 views

Find the minimum cost spider joining a root to some leaves

16 votes
1 answer
502 views

How expensive may it be to destroy all long s-t paths in a DAG?

Browse more Questions