0
votes
0answers
42 views

Computing a Levenshtein edit distance between two strings when a particular set of string edits is forbidden

Let's imagine we'd like to compute a Levenshtein edit distance between two strings, $S_1$ of length $n_1$ and $S_2$ or length $n_2$, consisting of characters over a finite alphabet $R$ of size $q$ ...
1
vote
0answers
88 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
0answers
48 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 ...
4
votes
4answers
311 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 ...
3
votes
0answers
126 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
0answers
88 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 ...
6
votes
1answer
228 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$; ...
2
votes
1answer
198 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 ...
6
votes
0answers
135 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 ...
9
votes
1answer
393 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 ...
1
vote
2answers
106 views

Draws from multiple non-disjoint urns

Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with ...
21
votes
3answers
1k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
1
vote
1answer
113 views

Generating k-partite graphs

Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...
4
votes
0answers
152 views

Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected ...
2
votes
3answers
135 views

Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
7
votes
2answers
298 views

Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...
5
votes
1answer
436 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
4
votes
0answers
235 views

Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$. It ...
2
votes
5answers
762 views

Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details. Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, ...
4
votes
1answer
215 views

Generating non-isomorphic graphs by adding edges to a given graph

Hello! This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here! I am given a fairly large graph $G$ and ...
0
votes
2answers
240 views

Creating composite rank [closed]

Problem: Suppose that $K$ different students are ranked based on $N$ different parameters (such as Physics marks, English marks, Biology marks, IQ etc). The rank under each parameter can be repetitive ...
2
votes
1answer
184 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
0
votes
1answer
93 views

Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.: (1) Each $q_i \in ...
1
vote
0answers
89 views

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard? Equally interesting would be to learn about such problems with a ...
2
votes
0answers
162 views

A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first. Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...
0
votes
1answer
234 views

Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $ and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $ I need to find the better algorithm which answers ...
1
vote
1answer
185 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
1
vote
1answer
122 views

How to deconstruct a sum of intersecting upsets

A set system $\mathcal{U}\subset P([n])$ is an upset if $B\supset A \in \mathcal{U}$ implies $B\in \mathcal{U}$, intersecting if $A,B\in\mathcal{U}$ implies $A\cap B \ne \emptyset$. Note that a ...
15
votes
4answers
752 views

Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem: Show, for all integers $1 \leq i \leq k$, that the univariate ...
1
vote
2answers
136 views

Approximate version of a balanced incomplete block diagram

Let $S$ be a set of some size $n$. I'm interested in knowing about combinatorial designs that are approximately balanced incomplete block designs, that I want a collection of subsets $C$ of $S$ such ...
1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2
votes
1answer
101 views

A Parameter related to fractional chromatic number and Kneser Graphs

Let $t \gt 0$ be an integer and $G$ is a simple graph with $\chi_f(G) = t$. Then $t$= inf $\{ \frac{n}{k}| G \rightarrow KG(n,k)\}$ where $KG(n,k)$ is the Kneser graph. Does there exist a $k$ such ...
2
votes
1answer
431 views

#P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
2
votes
1answer
163 views

Covering set problem

All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question --- Suppose we have $k$ sets $X_1,…,X_k$ which are subsets of a ...
4
votes
1answer
191 views

Consistency of systems of inequalities involving only differences

I have a very large number (670 billion) of systems of inequalities of the form: $C_1 - C_2 < C_4 - C_3 \wedge C_3 - C_2 < C_5 - C_3 \wedge ...$ where the $C_i > 0$. Ie. each system of ...
12
votes
0answers
293 views

Best known constant for parallel sorting

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...
4
votes
1answer
169 views

A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma

The general form of the Local Lemma can be stated as follows: Let $\mathcal{A}$ be a finite set of events in a probability space. For $A \in \mathcal{A}$, let $\Gamma(A)$ be a subset of ...
8
votes
3answers
432 views

Equitable Allocation of Individuals to Positions

I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction. The ...
4
votes
2answers
480 views

Getting started: combinatorial optimization for computer scientists

I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems. I have good knowleges of graphs, *-flow algorithms and so ...
2
votes
2answers
258 views

algorithms for comparing two simplicial complexes

Given a set $A$ of subsets of $\{1, \ldots n\}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and ...
3
votes
0answers
242 views

3-SAT and a matrix of linear forms representing a non-degenerate matrix

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question. As before, let $k$ be a field with $p$ elements. Consider the ...
4
votes
1answer
410 views

determining if a matrix of linear forms represents a non-degenerate matrix

Let $k$ be a field with $p$ elements. Consider the following computational problem Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots ...
6
votes
2answers
342 views

finding the $n$ closest pairs between $2n$ points

Given $2n$ points $x_1, x_2 \ldots x_{2n}$ and a distance $d_{i,j}$ defined between them, how can I best find the set $P$ of mutually exclusive pairs $(i,j)$ such that the sum of their distances $$ ...
1
vote
1answer
596 views

Applications of ham sandwich type results. References? A general principle?

Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any ...
0
votes
0answers
385 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where ...
2
votes
0answers
329 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of ...
7
votes
4answers
1k views

Stirling Number of first kind : Implementation

Hi everybody, Does there exist an explicit formula for the Stirling Numbers of the First Kind which are given by the formula $$ x(x-1)\cdots (x-n+1) = \sum_{k=0}^n s(n,k)x^k. $$ Otherwise, what is ...
6
votes
4answers
1k views

Constructing Steiner Triple Systems Algorithmically

I want to create STS(n) algorithmically. I know there are STS(n)s for $n \cong 1,3 \mod 6$. But it is difficult to actually construct the triples. For STS(7) it is pretty easy and but for larger n I ...
4
votes
1answer
258 views

Computing Simultaneous Hamming Neighborhood for a Set of Strings

Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming ...
3
votes
0answers
470 views

Covering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?

As a straightforward generalization of IMO Shortlist 2001 problem C4, we can show the following fact: Let $u$ and $v$ be two positive integers. A set of three integers $\left\lbrace ...