Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
65 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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] ...
user avatar
  • 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 ...
user avatar
  • 5,055
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
user avatar
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 ...
user avatar
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 ...
user avatar
14 votes

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into ...
user avatar
  • 141
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 ...
user avatar
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, ...
user avatar
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$. ...
user avatar
13 votes

How big is the variance of the treewidth of a random graph in G(n,p)?

You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You ...
user avatar
  • 231
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 ...
user avatar
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.
user avatar
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 ...
user avatar
11 votes

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Here are some additional examples to Mon Tag's answer : The Disconnected Cutset problem (Does $G$ admit a set of vertices $S$ such that $G-S$ and the subgraph of $G$ induced by $S$ are disconnected) ...
user avatar
  • 4,828
11 votes
Accepted

Sum of products of all combinations?

Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the ...
user avatar
  • 3,844
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 ...
user avatar
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, ...
user avatar
  • 311
11 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 ...
user avatar
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: ...
user avatar
10 votes

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

From the comment above: in Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs: GI is polynomial time (trivially) solvable for $(K_s,...
user avatar
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 ...
user avatar
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,...
user avatar
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 ...
user avatar
  • 13.5k

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