New answers tagged


split every vertex $v$ into $v'$ and $v''$ and connect $v'$ to the incoming arcs and to $v''$, connect $v''$ to the outgoing arcs of $v$; set the flow constraints for $(v',v'')$ to $[0,a_v]$. If all other flow constraints are $[0,1]$ then, because of the integrality of the mincost flow problem the constraints on the number of active arcs will be met.


The triviality problem (input: a finite group presentation of a group $G$, output: yes/no according to whether $G$ is a trivial group) is not solvable by an algorithm. Indeed just apply the Adian-Rabin theorem to the property "being trivial". Now we deduce the general case of your question as follows: Suppose by contradiction that you have an ...


The function $f(x)$ is closely related to the notion of autocorrelation, which for a binary sequence $x$ of length $|x|=N$ and shift $w$ can be expressed as $$\textbf{AC}_x(w) := N - 2H(x\oplus R(x,w)).$$ The values of $\textbf{AC}_x(w)$ for various non-trivial shifts (i.e. $1\leq w\leq N-1$) are called out-of-phase autocorrelation values. So, $$f(x) = \min_{...


Suppose x contains n 1’s, and y is a cyclic shift of x. Suppose that there are exactly m positions where both x and y have 1’s. Then x XOR y has 2(n-m) 1’s. Thus f(x) is always even. Thus a necessary condition for H(x) = f(x) = n is that n is even. Consider the length 4 sequence x = 0110. The cyclic shifts are x_1=1100, and x_2=1001, and x_3 = 0011, so that ...


Adding to Sean Lawton's answer, there was an arxiv posting yesterday by Davies-Juhász-Lackenby-Tomasev, The signature and cusp geometry of hyperbolic knots that describes a relation between the cusp geometry of a hyperbolic knot, its signature, and its hyperbolic volume. The authors describe how this was found via machine learning. This is not exactly what ...


I saw two articles today (12/2/21) that reminded me of this post. I am mentioning them here to potentially help the OP: Learning knot invariants across dimensions by Jessica Craven, Mark Hughes, Vishnu Jejjala, Arjun Kar (on arXiv) DeepMind’s AI helps untangle the mathematics of knots, by Davide Castelvecchi (on


One can also completely break this key exchange (and a more general key exchange algorithm) using linear algebra. Consider the following key exchange algorithm. Suppose that $\mathcal{A}_{L},\mathcal{B}_{L}$ are sets of $m\times m$-matrices and $\mathcal{A}_{R},\mathcal{B}_{R}$ are sets of $n\times n$-matrices. Let $C$ be a publicly available $m\times n$-...


pyMCFSimplex seems to best fit my needs. "It is a free Python port of a Python Wrapper for MCFSimplex. pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) ...


This protocol as it is stated is broken using a quotient attack. I am going to explain this technique in as general of a context that I can (this idea should also break generalizations of this protocol). Suppose that $X$ is a set. Let $G,H$ be monoids that act on $X$. Here $G$ acts on $X$ on the left so that $gx\in X$ whenever $g\in G,x\in X$, and $H$ acts ...


You may want to take a look at this article . The article is both entertaining and well written, and here are its core ideas: KNOTS AS WORDS IN A LANGUAGE First core idea is to leverage the representation of knots as phrases in a suitable language. This is the cool part of the article, and actually a good recap of the fundamentals of Knot Theory, so I ...


The answer is false. Let $G$ be the 3-prism and $\varphi$ the coloring shown below. $G$ cannot have a 2-distance vertex 4-coloring. As all pairs of vertices in $G$ have distance either 1 or 2, a 2-distance coloring of $G$ would require 6 colors.


Here is a section on graph theory in A compendium of NP optimization problems by P. Crescenzi and V. Kann.


A site dedicated to graph classes, including the computational complexity of associated problems, is

7 $$ \quad\quad\quad\quad\quad\quad\quad\quad $$

Top 50 recent answers are included