The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

Filter by
Sorted by
Tagged with
6
votes
0answers
160 views

Positive cut algorithm on bipartite graphs with negative weights

Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
4
votes
1answer
159 views

Complexity of counting maximum number of co-linear points in Euclidean plane

The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points. I already know that the problem can be solved in quadratic time using hashing or projective ...
4
votes
1answer
112 views

Base extension in residue number systems with low space

Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes ...
9
votes
1answer
330 views

Pattern matching with don't cares: multiple patterns

Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution. But what happens ...
8
votes
0answers
297 views

Complexity of $k=2$ set packing

I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem: Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ...
1
vote
0answers
83 views

Constant time Lookup for Inversion Problem

I'm trying to figure out how to compute all the significant inversions $(i,j)$ in a list $l = [a_1, \ldots a_n]$ where an inversion $(i,j)$ is significant if $i < j$ but $a_i > 2a_j$. Now there ...
7
votes
1answer
288 views

Free books (or course materials) on undergraduate algorithms

What free books (or course materials) are there that cover undergraduate algorithms material? I added "course materials" in case there exist comprehensive sets of lecture notes/video/other that are ...
2
votes
1answer
249 views

Complexity involving connected components of 0/1 matrix

Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you ...
6
votes
1answer
256 views

Find a string with minimal edit distance from a set of given strings

Input: a bunch of binary strings: x_0, x_1, ... , x_n Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. ...
5
votes
1answer
336 views

Fast Algorithm to Check if a Set of Sets forms an Anti-chain

Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ ...
8
votes
1answer
287 views

Are there poly time algorithms to determine if a graph is almost bipartite?

Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite. Are there poly time algorithms to determine if a graph is exactly or ...
6
votes
1answer
257 views

For a given binary-search tree obtain an isomorphic splay tree

I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en....
3
votes
1answer
283 views

Enumerating all simply typed lambda terms of a given type

How can I enumerate all simply typed lambda terms which have a specified type? More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ...
12
votes
2answers
808 views

Memory requirement for fast matrix multiplication

Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + ...
9
votes
1answer
286 views

Evaluate boolean circuit on batch of similar inputs

Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2. Let $x \in \{0,...
3
votes
0answers
241 views

Approximating the VM packing problem

In the wikipedia article on bin-packing it is stated that A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
2
votes
1answer
84 views

Density of multiples

I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the ...
5
votes
1answer
167 views

Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
6
votes
2answers
393 views

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
-2
votes
1answer
96 views

Proving hardness of approximation with reduction in terms of 1/$\epsilon$

I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
2
votes
1answer
258 views

List of Pivot rules for simplex methods

Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
9
votes
1answer
299 views

How is the inner ring chosen in the Schönhage–Strassen algorithm?

I've been trying to implement the Schönhage–Strassen integer multiplication algorithm, but hit a stumbling block in the recursive step. I have a value $x$ with $n$ bits and I want to compute $x^2 \...
12
votes
0answers
166 views

What is the curve of “search vs. insert”

Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time. With this ...
5
votes
2answers
187 views

Solution/Hardness of the following (integer) budgeted problem?

I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion! Assume there are $N$ startups. For each startup $i$, you can invest $x_i\...
2
votes
2answers
276 views

Is there research on algorithmic design patterns?

From what I've seen in the majority of algorithms publications, the focus of research is mainly towards improving the solutions to algorithmic problems in terms of efficiency or optimality in the case ...
5
votes
0answers
109 views

Algebraic dependence of roots of irreducibles over a finite field

I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
0
votes
1answer
170 views

Efficient update of reachable set of a node in a digraph

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , ...
3
votes
4answers
244 views

Find the maximum subset contained by a ball of radius R

I am searching for the name of / literature to the algorithmic problem as follows: Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, ...
0
votes
1answer
216 views

Paritioning a graph into clique and independent set

I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
2
votes
1answer
332 views

Graph planarity testing via adjacency matrix

I have looked at several efficient graph planarity algorithms which rely on computing and traversing DFS trees (that add one vertex/edge/path at a time). I am looking for graph planarity algorithms ...
7
votes
1answer
355 views

Complexity of “destroying” the graph's minimum spanning tree weight

Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$. Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
5
votes
1answer
203 views

Algorithm/Complexity for the following SAT Version

Given : A 3 SAT problem. Known 1 : The SAT problem is satisfiable. Known 2 : We have a solution that satisfies the given 3 SAT. Problem Statement: Maximize the solution, i.e. find a solution such ...
2
votes
2answers
538 views

Subset product problem

We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$. You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)...
4
votes
1answer
145 views

Maximum common subgraph of two planar graphs of bounded degree k

Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar ...
0
votes
0answers
68 views

Trade-off between number of spheres and wasted space in covering a 3d object by spheres

Consider the following optimization problem: Input: a 3-dimensional "object" $O$. Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
7
votes
1answer
142 views

Label-disjoint paths in directed graphs

Checking if there are two edge-disjoint paths from $s$ to $t$ in a given undirected graph $G$ is in P via a standard solution based on maxflow. I am interested in the complexity of the following ...
5
votes
3answers
446 views

Beating naive dynamic programming: examples similar to integer partitions?

Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming ...
2
votes
0answers
159 views

Non-Linear Programming with \min operator in the constraint

Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1. \begin{align} \text{maximize } &\sum_{i,j=1}^{m,n} c_{ij}...
5
votes
0answers
129 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths. Given a graph $G = (V, E)$ ...
2
votes
1answer
187 views

Is there any efficient algorithm for computing all semigroups of order n? [closed]

Is there any efficient algorithm for computing all semigroups of order n? I found the following paper which solves a bit different problem. Veronique Froidure and Jean-Eric Pin, "Algorithms for ...
6
votes
2answers
227 views

Parametrized complexity of the 2-Long Paths Problem

Consider the following problem: Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$...
11
votes
3answers
719 views

Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

In a read-twice opposite CNF formula each variable appears twice, once positive and once negative. I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of ...
3
votes
3answers
172 views

Canonisation of boolean matrices under row and column permutations

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows: $A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\...
1
vote
1answer
217 views

Packing sets to maximize overlap

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$. Consider the following problem: Input: a list of $m$ weights $w = (w_1, \ldots, w_m)$, a list of $n$ distinct subsets $T = (S_1, \ldots, ...
2
votes
2answers
286 views

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such ...
2
votes
1answer
145 views

Minimum weights needed to derandomize weight assignment by isolation lemma

Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight ...
6
votes
0answers
160 views

Machine learning algorithms on hypergrap models

Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two ...
5
votes
1answer
147 views

Does k-PATH admit a constant approximation?

In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$. A $\alpha$-approximation for $k$-PATH is an ...
10
votes
0answers
218 views

Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?

Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
1
vote
0answers
115 views

Computing $a^e \mod p^n$ Efficiently

It is well known that we can compute: $$ a^e \mod m $$ in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering ...