66 votes
Accepted

The origin of the notion of treewidth

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a ...
43 votes
Accepted

Is it a rule that discrete problems are NP-hard and continuous problems are not?

An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$ This at ...
  • 2,295
26 votes

Is it a rule that discrete problems are NP-hard and continuous problems are not?

There are many continuous problems of the form "test whether this combinatorial input can be realized as a geometric structure" that are complete for the existential theory of the reals, a continuous ...
23 votes
Accepted

Is it decidable to determine if a given shape can tile the plane?

According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] ...
  • 516
19 votes
Accepted

$d$-regular bipartite expander graph

There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a ...
  • 5,190
18 votes
Accepted

Is Hartmanis-Stearns conjecture settled by this article?

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn". Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
17 votes
Accepted

Additive combinatorics applications in algorithm design

Timothy Chan and Moshe Lewenstein have a paper on 3SUM and related problems in the upcoming STOC, which applies an effective version of the BSG theorem from additive combinatorics to solve variants of ...
17 votes

Math talk: Theorem about git revision control system?

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and arose in the ...
16 votes
Accepted

Is optimally solving the n×n×n Rubik's Cube NP-hard?

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
16 votes
Accepted

Math talk: Theorem about git revision control system?

A git repository can be thought of as a partially ordered set of revisions (where one revision is earlier than another in the order if it is a direct or indirect successor of the earlier one). The ...
15 votes

Throwing Balls into Bins, estimate a lowerbound of its probability

The answer is $\Theta(\sqrt{n})$. First, let's compute $E_{n-1}$. Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability ...
14 votes
Accepted

Is there notation for converting a multi-set to a set?

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here. Multisets are an awkward case of a perfectly natural mathematical ...
14 votes
Accepted

Permutations with forbidden subsequences

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the ...
14 votes

Is it decidable to determine if a given shape can tile the plane?

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, ...
14 votes
Accepted

Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
13 votes

Is it a rule that discrete problems are NP-hard and continuous problems are not?

While this doesn't exactly answer your original question, it's a (conjectural) example of a sort of philosophical counterpoint: a problem where the presentation is discrete but all of the hardness ...
13 votes
Accepted

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

I believe the problem to be coNP-complete. I have uploaded it as an arXiv preprint.
12 votes
Accepted

Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
12 votes
Accepted

Does the first order theory of a finite structure have bounded quantifier rank?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after ...
11 votes
Accepted

computing maximal bit density over a FSM

First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00 where there is no max. (The sup may not be attained.) Second, by "FSM" I ...
11 votes
Accepted

Random walk and mean hitting time in a simple undirected graph

I have decided to ask David Wilson himself, soon thereafter got a reply: For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, ...
  • 311
10 votes
Accepted

Grid minor in digraphs

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs. Stephan Kreutzer and Ken-ichi Kawarabayashi: ...
10 votes
Accepted

The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a ...
10 votes
Accepted

The asymptotic behavior of a recurrence related to stable matchings

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily. First,...
9 votes

Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...
9 votes

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. Later the base of the ...
  • 13.7k
9 votes
Accepted

Addding edges to spanning tree without destroying planarity

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of ...
9 votes
Accepted

Number of Automorphisms of a graph for graph isomorphism

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-...
9 votes
Accepted

VC dimension of polynomials over tropical semirings?

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
  • 6,635
8 votes

How many distinct colors are needed to lower-bound the choosability of a graph?

As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of http://arxiv.org/abs/1507.03495 improves upon the aforementioned result of Král' and ...
  • 1,952

Only top scored, non community-wiki answers of a minimum length are eligible