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.

Filter by
Sorted by
Tagged with
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 ...
Star21's user avatar
  • 51
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$ ...
lyrically wicked's user avatar
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. ...
lchen's user avatar
  • 459
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}$. ...
eddy ardonne's user avatar
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,...
Bean Guy's user avatar
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 ...
user avatar
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). ...
lchen's user avatar
  • 459
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 $...
Bean Guy's user avatar
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 ...
GSM's user avatar
  • 343
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 $...
joro's user avatar
  • 24.2k
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 ...
mc.math's user avatar
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 ...
W. Paul Liu's user avatar
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?
W. Paul Liu's user avatar
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 ...
jack's user avatar
  • 2,929
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
retg's user avatar
  • 21
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Bogdan Grechuk's user avatar
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 ...
user avatar
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 $...
user avatar
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.
Math-fort's user avatar
  • 103
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,...
Shaun Han's user avatar
  • 141
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 ...
meirs's user avatar
  • 21
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$ ...
Turbo's user avatar
  • 13.7k
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, ...
Zhukui Bai's user avatar
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 ...
Alexander Chervov's user avatar
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 ...
Bogdan Grechuk's user avatar
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 $...
westlon's user avatar
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 ...
Student's user avatar
  • 5,008
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 ...
The Bridge's user avatar
  • 1,304
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 ...
Bob's user avatar
  • 131
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$....
Gautam's user avatar
  • 1,693
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 ...
Rito's user avatar
  • 11
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 ...
N. Gast's user avatar
  • 552
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? ...
Turbo's user avatar
  • 13.7k
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.
Vo Hoang Anh's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Gautam's user avatar
  • 1,693
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 ...
joro's user avatar
  • 24.2k
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 ...
plegri's user avatar
  • 21
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 ...
Ak01's user avatar
  • 101
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 ...
joro's user avatar
  • 24.2k
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 $...
Avi Steiner's user avatar
  • 3,031
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 ...
Emanuel's user avatar
  • 21
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 ...
Manfred Weis's user avatar
  • 12.6k
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(...
emptysamurai's user avatar
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 ...
Xin Zhang's user avatar
  • 1,130
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|}...
Flore's user avatar
  • 59
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 ...
Pierre's user avatar
  • 171
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$ ...
joro's user avatar
  • 24.2k

1
3 4
5
6 7
32