# Tagged Questions

**25**

votes

**2**answers

430 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**1**

vote

**1**answer

58 views

### Heuristic for choosing n-vectors from n-sets

my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...

**4**

votes

**0**answers

129 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**10**

votes

**1**answer

343 views

### Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line ...

**2**

votes

**1**answer

135 views

### Galois Connections: algorithmic generation

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ?
I'm looking for references about this problem.

**3**

votes

**2**answers

140 views

### All Integers from the Smallest Digit Stream with a Window Filter

Let's represent integers with D digits where each digit has B values
(i.e., the base is B and we effectively work only with integers between
1 and B^D). Is it possible to choose a single ...

**8**

votes

**3**answers

541 views

### Changing combination lock [closed]

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...

**37**

votes

**1**answer

2k views

### improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...

**3**

votes

**1**answer

229 views

### Generalization of notion of convexity

I am searching for the correct term for the following, if it exists.
A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius ...

**2**

votes

**0**answers

88 views

### Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...

**3**

votes

**1**answer

124 views

### A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...

**5**

votes

**1**answer

193 views

### coin reversal puzzle with one hand and two stacks

Suppose that you have N labeled coins pinched in one stack in your fingertips
(your palm is above your fingers and your palm is facing down, so that you can
drop as many coins as needed from the ...

**3**

votes

**2**answers

237 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...

**0**

votes

**0**answers

71 views

### Find minimal set of progressions which intersections, unions or negations covers given set

Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline ...

**1**

vote

**1**answer

110 views

### Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...

**8**

votes

**2**answers

1k views

### get a point in polygon (maximize the distance from borders)

I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders ...

**2**

votes

**2**answers

316 views

### Integers up to n having an even number of trailing zeros in their factorial

It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$
Now assume that we want ...

**0**

votes

**0**answers

80 views

### Minimize the length of two disjoint segments in the string with given property

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z.
...

**3**

votes

**1**answer

379 views

### Random weighted selection without replacement

I am using the following procedure to select $m$ different numbers $\{i_1,\ldots,i_m\}$ from the set $\Omega = \{1,\ldots,N\}$, with $m,N\in\mathbb{N}$ such that $m< N$.
Selection procedure
...

**4**

votes

**4**answers

540 views

### Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed.
I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...

**2**

votes

**0**answers

63 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...

**2**

votes

**0**answers

36 views

### largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...

**2**

votes

**0**answers

171 views

### Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...

**3**

votes

**0**answers

161 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...

**3**

votes

**1**answer

234 views

### How to perform Importance Sampling with Prior Information

Let us define a random variable $X$ with density function $p(x)$. We wish to calculate $\mathbb{E}[f(X)] = \int f(x)p(x)dx$. We can compute the expectation by Monte Carlo simulations as
...

**4**

votes

**0**answers

107 views

### Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...

**0**

votes

**0**answers

70 views

### approximate coordinates in a one dimensional lattice

suppose I have a finite set of real numbers ${r_1, \ldots r_n \in \mathbf{R} }$ and a single real number $x \in \mathbf{R}$. Is there a fast algorithm for finding integer numbers ${i_1, \ldots i_n \in ...

**4**

votes

**1**answer

209 views

### Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

Is there any known efficient algorithm (something that works better than brute-force algorithm) to check that given a $(0,1)$-$d \times d$ matrix $A$, is there a permutation matrix $P$ of the same ...

**4**

votes

**1**answer

203 views

### Details of generation programs supplied with nauty

The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was ...

**1**

vote

**4**answers

953 views

### Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...

**5**

votes

**1**answer

396 views

### Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task:
Let $\mathbb{F}$ be a finite field.
Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let
$G=\langle ...

**4**

votes

**2**answers

805 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**12**

votes

**2**answers

530 views

### Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...

**3**

votes

**2**answers

195 views

### Equipartition of the circle [closed]

Browsing an old technical studies pupil's school book, I have found the description of a method to place at equal distance $N$ points on the circumference of a circle. I am looking for a proof of this ...

**3**

votes

**2**answers

272 views

### Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?

**2**

votes

**1**answer

288 views

### efficient arithmetic with (short) Conway games?

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations ...

**1**

vote

**0**answers

53 views

### Finding special vectors generated by a matrix

Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix.
Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...

**1**

vote

**0**answers

52 views

### Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$.
2) Also, in general setting, the problem is to ...

**6**

votes

**0**answers

146 views

### Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...

**1**

vote

**1**answer

189 views

### Finding particular reduced words for Weyl group elements

I am studying cluster algebra structures on the coordinate rings of partial flag varieties, as defined in the paper Partial flag varieties and preprojective algebras by Geiss, Leclerc and Schröer. One ...

**2**

votes

**1**answer

199 views

### Are there any good techniques for calculating Hausdorff measure?

I'm aware that many techniques have been developed for the purpose of calculating Hausdorff dimension (although I'm fairly unfamiliar with them), but my question is whether or not we have any good ...

**12**

votes

**1**answer

539 views

### Stable matchings when switches have costs

The Gale-Shapley algorithm finds a stable matching in the complete bipartite graph, for any preference matrix. It's also well-known that stable matchings don't always exist in the complete graph ...

**0**

votes

**1**answer

220 views

### Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...

**8**

votes

**1**answer

814 views

### How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...

**-2**

votes

**1**answer

245 views

### Polygon Problem [closed]

There are $N$ regions which are numbered from $1$ to $N$. Each region is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. ...

**7**

votes

**2**answers

317 views

### How do I efficiently find a sequence of Reidemeister moves between equivalent link diagrams?

In knot theory, two link diagrams are equivalent if and only if they can be related by performing a finite number of Reidemeister moves. But sometimes it is so confusing that I don't know which type ...

**0**

votes

**1**answer

239 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**1**

vote

**1**answer

217 views

### Set of distributions that minimize KL divergence,

Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence,
is there a ...

**6**

votes

**4**answers

547 views

### How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...