For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, Knuth (1976) gives an infinite family of instances with $\Omega(2.28^n)$ ...

Computer Science Unplugged addresses kids (and teachers) in primary school.

Daniel Král and Jiří Sgall answered your question to the negative. From the abstract of their paper: A graph $G$ is said to be $(k,\ell)$-choosable if its vertices can be colored from any lists $L(... View answer Accepted answer 21 votes The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of$n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra ... View answer Accepted answer 19 votes It is proved in [1, Corollary 7], that 3-partition is strongly NP-hard when the integers$a_1, \ldots, a_n$are all distinct. The bounds$B/4 < a_i < B/2$are not imposed in , but this should ... View answer Accepted answer 17 votes One example is Maximum Independent Set. It is NP-hard to approximate the problem with ratio$n^{1-\epsilon}$(Zuckerman, 2007). However, Bourgeois et al. (2011) give a simple$n^{1/2}$-approximation ... View answer 17 votes There is a recent survey Habib and Paul (2010). A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1): 41-59 (2010) that you should check out. View answer Accepted answer 16 votes There are several connections between parameterized complexity and approximation algorithms. First, consider the so-called standard parameterization of a problem. Here, the parameter is what you ... View answer 15 votes I basically agree with you, with just a tiny modification: A graph$G$is a$k$-tree if and only if either$G$is a complete graph with$k+1$vertices, or$G$has a vertex$v$such that the (open) ... View answer Accepted answer 15 votes The #VC problem of computing the number of vertex covers of a given graph remains #P-hard for 3-regular graphs; see for example [Greenhill, 2000]. To show that the #VC problem remains #P-hard for ... View answer 13 votes In the Graph Homomorphism problem, the input is two graphs$G$and$H$and the question is whether there is a mapping$h$from the vertices of$G$to the vertices of$H$such that for every edge$uv\...

The Tractable Cognition thesis postulates that human cognitive capacities are constrained by computational tractability. In this way, the P-Cognition thesis uses deterministic polynomial time as a ...

Suppose $G$ is a triangle-free star-cutset-free circle graph. I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges. Consider a circle representation $... View answer Accepted answer 11 votes An early example is the W-hardness proof for Tournament Dominating Set (Theorem 4.1 in ). The reduction is from Dominating Set and it constructs a tournament with$O(2^k n)$vertices, where$n$... View answer 11 votes The problem is known as r-Set Packing: Instance: A collection$\mathcal{C}$of subsets of size at most$r$of a finite set$S$and an integer$k$. Parameter:$k$Question: Is there a subcollection$\...

PhD positions in TCS and Discrete Math are sometimes announced on TheoryNet and DMANET. These are mailing lists to circulate announcements and questions regarding conferences, workshops, seminars, ...

Suppose $H$ has at least two vertices. The family of all $H$-free graphs is hereditary on induced subgraphs and the property of being $H$-free is non-trivial, where a property is non-trivial if it is ...

It is also at most as hard as $k$-coloring a graph $G=(X,E)$, where $E$ is formed by making each $X_i$ into a clique. Your restriction that all $X_i$ are of size $k$ means that you can cover each edge ...

The problem is polynomial-time solvable. Say that a vertex is balanced if its in-degree equals its out-degree. Note that a directed graph is Eulerian iff every vertex is balanced and its underlying ...

I believe the most standard term is complete multipartite graph.

Basically, Max 2-CSP on $n$ variables and $n$ randomly chosen constraints can be solved in expected linear time (see the reference below for the exact formulation of the result). Note that Max 2-CSP ...

As David pointed out, you basically ask for bounds on the treewidth of a connected graph with average degree 3. For the more special case of 3-regular graphs, the following lower and upper bounds can ...

EDIT: As pointed out by Ryan in the comments, a problem may have a nonuniform algorithm with running time $O(2^{\epsilon n})$ for any constant $\epsilon > 0$ (the algorithm has access to $\epsilon$)...

Adaptive Analysis measures the running time of polynomial time algorithms with respect to a multitude of parameters. For example, you want a sorting algorithm that runs in time $O(n \log n)$, but is ...

This only aims at partially answering the first question of the post: What are some directed problems that remain NP-hard on DAGs ? In , a few natural problems on directed graphs are given that ...

This only complements David's answer, who shows that the number of connected induced subgraphs can be enumerated with polynomial delay. Since a complete graph on $n$ vertices has $2^n$ connected ...

You are looking for an output-polynomial algorithm for enumerating minimal transversals of hypergraphs (or hitting sets for set systems). According to Golovach et al. (ICALP 2013), The question ...

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$. Consider the integer program $I_n: 1 \le x\le 2^n$ with the integer variable $x$. So, $k=1$ and the program can be ...

Williams (2009) [arXiv version] gives a randomized $2^k poly(n)$ time algorithm finding a path of length at least $k$ in a graph on $n$ vertices. The paper contains pointers to previous deterministic ...