Questions tagged [algorithms]
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1,562
questions
1
vote
1
answer
79
views
Deduce unsolvability of $\operatorname{IP}(G_0)$ from the Adian–Rabin Theorem
$\operatorname{IP}(G_0)$: the special isomorphism problem for $G_0$, i.e., given $G_0$, determine if $G$ is isomorphic to $G_0$. My question is that how can we deduce from the Adian–Rabin theorem that ...
7
votes
2
answers
308
views
Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?
Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $x$ ...
1
vote
0
answers
61
views
A variant of node-disjoint path problem
Given a graph $G$, I want to find $2$ (or $k$) node-disjoint paths with minimum total cost (or minimum maximum cost). The problem is a classical problem, but I have the following non-trivial setting. ...
2
votes
0
answers
118
views
Finding elements in a real extension of $\mathbb{Q}$ that are close to some number in $\mathbb{R}$
Let's consider a set of numbers that one knows to high precision, and one knows or has a strong suspicion that `exact versions of these numbers' (see below) belong to a real extension of $\mathbb{Q}$. ...
0
votes
0
answers
136
views
Binary polynomial evaluation
Let $p$ be a prime number and let $P(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ be a polynomial in $\mathbb{Z}_p[x]$ with binary coefficients, i.e., such that $a_i \in \{0,1\}$ for all $i = 0,...
3
votes
0
answers
176
views
Enumeration of stable graphs of genus $g$
Let $G=(V,E)$ be a connected undirected finite graph, let us call $G$ stable if each vertex has degree at least $3$.
Is there a computer algorithm to efficiently enumerate (repetition allowed) all ...
3
votes
0
answers
213
views
Max flow with minimum number of edges
A max-flow problem may have multiple solutions. Among these max-flows, I seek the one with the minimum number of positive flow edges (by positive flow edges I mean the edges carrying positive flow). ...
1
vote
0
answers
131
views
Polynomial interpolation of binary vectors
Let $\mathbb{F}$ be a finite field and let $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ be $n$
pairwise distinct points in $\mathbb{F}$.
Given the vector $\boldsymbol{y} = (y_1, y_2, \dots, y_n)$, with $...
10
votes
3
answers
1k
views
Deep learning for knot theory. Classification
As far as I know, there is a classification of all prime knots with less than 16 crossings.
It seems that there is already a fast enough algorithm to distinguish a knot from an unknot.
So in principle ...
5
votes
2
answers
494
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...
0
votes
0
answers
87
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
1
vote
1
answer
96
views
A sufficient condition for a subcubic graph having a 2-distance vertex 4-coloring
Let $G$ be a subcubic graph with only vertices of degree 1 or degree 3.
Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that
each edge is colored with a set of ...
9
votes
3
answers
1k
views
Is there a website or a survey collecting all NP-complete problems on graph theory?
I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
2
votes
0
answers
100
views
Decomposing a planar graph
Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
0
votes
0
answers
81
views
Perfectly balanced spanning trees
I call a spanning tree perfectly balanced if, after a two-coloring of the tree-graph's vertices
the two vertex sets that are defined by the assigned colors have equal cardinality and
the two vertex ...
2
votes
0
answers
74
views
Reduce SAT to SAT with at most one satisfying assignment in polynomial time
Is it possible to turn, in polynomial time, a SAT instance into a SAT instance that is unsatisfiable if the original was unsatisfiable and that has exactly one satisfying assignment if the original ...
0
votes
0
answers
119
views
What does it mean to find an efficient algorithm for NP complete problems
Suppose I have a problem $P$, an instance $I$ and an algorithm $A$ that efficently solves $P$ for $I$.
Let $P'$ be $P$ with additional constraints that are violated if $A$ is applied to $I$ and ...
2
votes
0
answers
243
views
Integer points on genus 1 curves using CAS
How can I practically find integer points on genus 1 curves with small coefficients using computer algebra systems (CAS), like Mathematica, Maple, SageMath, Magma, etc.?
As a specific example, do ...
0
votes
0
answers
79
views
3-SAT family with $\omega(n^2)$ time complexity
A 3-SAT family is an algorithm that given a positive integer $n$ outputs a 3-SAT problem in $n$ clauses in $O(n^{1+\epsilon})$ time ($\epsilon$ is to allow for the indexing of the variables).
A ...
2
votes
1
answer
116
views
Family of PTIME sets where it is hard to name elements
Call a function$$\mathbb{N}\times \mathbb{N}\to \{0, 1\}, \quad (n, m)\to f(n, m)$$computable in polynomial time in $\log n+\log m$ a PTIME family.
Given a PTIME family $f$ call a computable function $...
4
votes
0
answers
133
views
Given a large number $n$, check if it has a zero digit in base $b$
Given a large number $n$, check if it has a zero digit in base $b$. By large number I mean something like $2^{13579^{3597}}$ so direct computation of digits is not feasible.
1
vote
0
answers
170
views
What is a good algorithm to measure similarity between isomorphic graphs with different node labels?
I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...
2
votes
0
answers
71
views
Minimum size of a Diophantine equation detecting the emptiness of a recursive set
I have a program $P$ taking an integer as input and outputting a Boolean value. It runs in polynomial time in the length of the input.
There necessarily exists a Diophantine equation that has a ...
0
votes
1
answer
444
views
Method to solve modular quadratic polynomial [duplicate]
If $q$ is a prime what is the best method to compute roots of a quadratic polynomial $f(x)\equiv0\bmod q^2$ which is of form $x^2+bx+c\equiv0\bmod q^2$ where $b^2-4c\equiv0\bmod q$ and $gcd(b,q)=1$ ...
2
votes
1
answer
112
views
$W[1]$-hard and FPT about the equitable tree-coloring problem
I am confused by the two conclusions in this paper (DOI link behind paywall at Springerlink).
It shows that the equitable tree-coloring problem is $W[1]$-hard when parameterized
by treewidth.
However, ...
20
votes
5
answers
3k
views
How can you find an integer coefficient polynomial knowing its values only at a few points (but requiring the coefficients be small)?
Example: How can you guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this ...
5
votes
0
answers
202
views
Integer points of rational function in 2 variables
Is there an algorithm that, given polynomials $P(x)$ and $Q(y)$ with integer coefficients, decides whether there exists integers $x$ and $y$ such that $\frac{P(x)}{Q(y)}$ is an integer?
This is a ...
0
votes
1
answer
136
views
Computationally intractable orbit of a monoid action on a finite set
Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.
A characterization of $M_n$ is an algorithm that takes an integer $...
4
votes
1
answer
98
views
Normal form of framed links under Kirby moves
It's well known that any oriented closed 3-manifold (topological or smooth) can be obtained by surgerizing along a (framed oriented) link $L$ in the 3-sphere $S^{3}$. Even better, Kirby found a ...
1
vote
1
answer
181
views
Sampling uniformly in a ball of radius $\epsilon$ in the space of dicrete r.v. of m modalities for the total variation metric
I am looking for some reference or an algorithm that allows to sample uniformly in the ball centered at a discrete random variable of n modalities in the TV distance.
For the record for 2 discrete ...
3
votes
0
answers
103
views
Next smooth number
I want to find the next $n \in \mathbb{N}$ such that
$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$
Where $\mathbb{P}_B$ is the set of primes not greater than $B$
I know that we can generate ...
3
votes
0
answers
103
views
Efficient computation of "higher order" Jacobi symbols
Let $N> 1$, and suppose $a \in (\mathbb{Z}/N\mathbb{Z})^{\times}$. There are efficient algorithms to compute the Jacobi symbol $\left(\frac{a}{N}\right)$ using quadratic reciprocity. Fix $k \geq 1$....
1
vote
0
answers
37
views
Enumerating Independent Sets of Size $t=\Theta(n)$
Let $i_t(G)$ denote the number of independent sets of size $t$.
There is a bounds $i_t(G)$ for $t = \Theta(n)$(https://arxiv.org/abs/1204.3060.) in terms of minimum degree of $G$.
Q. Is there any ...
6
votes
2
answers
2k
views
Complexity of rectangular matrix multiplication
I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$.
From [Le Gall and Urrotia], I know that:
if $A$ and $B$ are square-matrices of size $n$, then this can ...
0
votes
0
answers
58
views
Hamming distance globally and Euclidean distance locally to a cycle
Given a permutation matrix 'the question is to decide if there is a permutation matrix representing a cycle within Hamming distance $d$ from given matrix'. Is there an efficient algorithm for it?
...
4
votes
0
answers
171
views
Faster Algorithm for counting non-negative triple $(a, b, c)$ satisfied $(a + b + c \le S)$ and $(a \times b \times c \le T)$ [closed]
Now this will be dicussed on (https://math.stackexchange.com/questions/4230187/faster-algorithm-for-counting-non-negative-tripplea-b-c-satisfied-a-b-c) only.
2
votes
0
answers
42
views
Calculating non-polynomial spline functions
Question:
what is known about the algorithmic construction of general interpolating spline functions with smoothness constraints at every knot?
So far I could only find descriptions for splining ...
1
vote
0
answers
537
views
Factoring $N$ given a solution to $x^2 + y^2 \equiv 0 \pmod{N}$
Let $N$ be a composite integer, and suppose we are given a randomly generated solution $(x, y)$ of the equation $x^2 + y^2 \equiv 0 \pmod{N}$. By randomly generated, I mean that $(x, y)$ is selected ...
1
vote
0
answers
176
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
2
votes
0
answers
59
views
Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.
Is there a polynomial-time algorithm for uniformly sampling from ...
0
votes
1
answer
1k
views
How does the greedy algorithm for CSES problem collecting numbers work? [closed]
The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds ...
2
votes
2
answers
304
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
3
votes
0
answers
49
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
2
votes
0
answers
129
views
Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions
playing around with stuff for my dissertation, I derived a quadratic problem in the general form
\begin{equation}
\begin{aligned}
\min_{x} \quad & x^TQx + c^Tx \\
\textrm{s.t.} \quad & Ax \leq ...
0
votes
1
answer
44
views
Name for a type of assignment task
given a bipartite graph $G(U,V,E\subseteq U\times V)$ with strictly positive edge-weights; is there an established name for the the task of calculating the lightest spanning subgraph and what is the ...
1
vote
1
answer
190
views
Coloring infinite graph made out of copies of a finite graph
I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically:
Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(...
2
votes
1
answer
93
views
What is the complexity of a special multigraph edge coloring problem
Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at ...
5
votes
1
answer
101
views
A method to bound distances between sets
I have two sets of points, $X$ and $Y$, which are finite and disjoint. I want to compute the distance between them defined by:
$$d(X,Y)= \frac{\sum_{x \in X} \|x-Y\| + \sum_{y \in Y} \|y-X\|}{|x|+|y|}...
0
votes
0
answers
36
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
2
votes
2
answers
372
views
Algorithm for finding integral points $P,n P$ on an elliptic curve
We found and implemented algorithm which finds integral points of infinite order $P=(X_1,Y_1)$
and $nP=(X_2,Y_2),n>1$ on an elliptic curve $E : y^2=x^3+a_4 x + a_6$.
Let $X(x)/Z(x)$ be the $X$ ...