# Tag Info

62

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 minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such ...

42

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 first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of ...

30

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials. Claim: The polynomials $\{ \prod_{i \in S} x_i : ... 26 Let$p$be a polynomial such that for all$x\in \{0,1\}^n$,$p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial$p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that, since the OR function is a symmetric boolean function, we have that for$k = 1, 2, \ldots, n$,$q(k) = 1$, and$q(0) = 0$. Since$q-1$is a non-zero ... 26 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 analogue of NP. In particular, this implies that these problems are NP-hard rather than polynomially solvable. Examples include testing whether a given graph is ... 23 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] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG] ... 21 There are several algorithms that count the simple paths of length$k$in$f(k)n^{k/2+O(1)}$time, which is a whole lot better than brute force ($O(n^k)$time). See e.g. Vassilevska and Williams, 2009. 20 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 (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem. Integer Linear Programming can be solved using$O(n^{2.5n+o(n)} \cdot L)$... 20 No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem$2$-Numerical Matching with target sums: Input: Sequence of$a_1, a_2, \ldots a_n$of positive integers,$\sum_{i=1}^n a_i = n(n+1)$,$1 \le a_i \le 2n$for$1 \...

19

It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007). B. Roberts and D. P. Kroese, "Estimating the number of $s$--$t$ paths in a graph". Journal of Graph Algorithms and Applications, 11(1):195-214, 2007. L. G. Valiant, "The ...

19

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 bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and ...

18

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 real time; in other words, the TM must compute the n'th digit in n time. Third, the result of Adamczewski et al. is only about finite automata and deterministic ...

17

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded clique-width.

17

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 3SUM faster than n^2 time. See this link to Chan's papers.

17

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 context of the DARCS version control system. It can be seen as an abstract theory of branching and merging. Recently patch theory has been given HoTT [ 6 ] and ...

16

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 partial orders that you get from git repositories tend to have low width (the size of the largest set of mutually independent revisions) because the width is ...

15

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

15

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 comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$....

15

There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in his book. A number of links have been found more recently as well, for example Kunal's blog post talks about the connection to differential privacy from [MN] and [NTZ]. Another example is Larsen's idea of using discrepancy to ...

14

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 triangles?). Other less trivial examples include: Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See: On stable sutsets ...

14

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, Robert T. Schweller, Andrew Winslow, Damien Woods; One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a ...

13

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 can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example, $\mathbb{P}( | tw(G(n,p)) - \mathbb{... 13 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 object which never really got a standard notation — likely because multisets took much longer to be interesting to logicians. As a corollary, there is no ... 13 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 comes from the 'continuous' aspect of the problem. The problem is the Sum of Square Roots problem: given two sets of integers$A=\{a_1, a_2, \ldots, a_m\}$and$B=...

13

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

13

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 triple to be between the other two. In your problem, the same constraint can be forced by forbidding all the subsequences on three elements that do not place the ...

12

In the paper Absolute Planar Retracts and the Four Color Conjecture, Pavol Hell proved several equivalente formulations for the 4CT. One of them reads as follows: Every planar graph is 4-colorable (The 4CT) iff there exists an absolute planar retract. (A subgraph $H$ of a graph $G$ is a retract of $G$ if there exists a homomorphism $r: V(G)\to V(H)$ ...

12

According to Wikipedia, the number of permutations in $S_n$ with exactly $k$ inversions is the coefficient of $X^k$ in $$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$ Denote this by $c(n,k)$. This shows that $$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$$ So the number of permutations in $S_n$ with at most $k$ inversions is equal to the number of permutations in $S_{n+... 12 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 which all quantifiers of the original formula can be simulated by conjunctions and disjunctions. In particular, the number of quantifiers (hence quantifier rank) ... 12 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\$. https://arxiv.org/abs/1410.1016 The proof is shorter than the one for grid minors but it is still not that that easy and builds on several previous tools. ...

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