Serge Gaspers
  • Member for 11 years, 5 months
  • Last seen more than a month ago
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Accepted answer
25 votes

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)$ ...

View answer
Concepts in theoretical CS that would be approachable ages 8-14
Accepted answer
24 votes

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

View answer
How many distinct colors are needed to lower-bound the choosability of a graph?
Accepted answer
23 votes

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
Integer programming with a fixed number of variables
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
Computational complexity of the 3-partition problem with distinct numbers
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 [1], but this should ...

View answer
Super-polynomial time approximation algorithms for optimization problems
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
References for Modular Decomposition
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
Relation between fixed parameter and approximation algorithm
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
What is the correct definition of $k$-tree?
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
Counting the number of vertex covers: when is it hard?
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
Problems with Unknown Single Exponential Time Agorithms
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\...

View answer
What is the complexity class most closely associated with what the human mind can accomplish quickly?
13 votes

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 ...

View answer
Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?
Accepted answer
12 votes

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
Instance of FPT-reductions that is not a polynomial-time reduction
Accepted answer
11 votes

An early example is the W[2]-hardness proof for Tournament Dominating Set (Theorem 4.1 in [1]). The reduction is from Dominating Set and it constructs a tournament with $O(2^k n)$ vertices, where $n$ ...

View answer
Is parametrized maximum independent clauses problem in FPT?
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 $\...

View answer
Monitoring PhD positions in TCS
10 votes

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, ...

View answer
Computation of max H-free sets
Accepted answer
10 votes

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 ...

View answer
"All-different hypergraph coloring" - known problem?
10 votes

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 ...

View answer
Complexity of the edge-disjoint cycle covers
Accepted answer
9 votes

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 ...

View answer
Terminology for complete k-partite graph where k is not fixed
9 votes

I believe the most standard term is complete multipartite graph.

View answer
Are there NP-complete problems with polynomial expected time solutions?
9 votes

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 ...

View answer
How large a treewidth can a tree plus half the edges have?
9 votes

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 ...

View answer
SERF-reducibility and subexponential algorithms
Accepted answer
8 votes

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$)...

View answer
Other kinds of running time analysis besides worst-case, average-case, etc?
8 votes

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 ...

View answer
Directed NP-hard problems on DAGs
Accepted answer
7 votes

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

View answer
enumerating all connected induced subgraphs
7 votes

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 ...

View answer
Is it known whether hypergraph minimal covers are P-enumerable?
Accepted answer
6 votes

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 ...

View answer
Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?
6 votes

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 ...

View answer
The number of cliques in a graph: the Moon and Moser 1965 result
6 votes

The answers that have been given so far are great. I thought I'd add some references. The Moon-Moser theorem was independently proved by Miller and Muller [1960] in a technical report. Wood [2011] ...

View answer
Finding the longest path between two nodes in a bidirectional unweighted graph
6 votes

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 ...

View answer