# Questions tagged [ds.algorithms]

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

1,646 questions
Filter by
Sorted by
Tagged with
1k views

### Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist? What are these problems called? Where can I find out more?
1k views

### Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
433 views

### Exact planar electrical flow

Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor. How quickly can we compute the exact effective resistance between two vertices in G? ...
848 views

### Multiplicative version of 3-SUM

What is known about the time complexity of the following problem, which we call 3-MUL? Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$? This problem is similar to ...
863 views

### Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank ...
4k views

### Maximum flow using Ford-Fulkerson and DFS

This question is about the time complexity of the Ford-Fulkerson maximum flow algorithm when using DFS to find augmenting paths. There is a well-known example showing that using DFS one can need a ...
609 views

### Educational Source or Survey on Analysis of Semidefinite Program?

When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms ...
1k views

### Generating a tower defense maze, aka Finding the K most vital nodes (“nodewise interdiction”) in an unweighted grid-graph

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually ...
1k views

### Detecting two kinds of almost-simple polygons

I'm interested in the complexity of deciding whether a given non-simple polygon is almost simple, in either of two different formal senses: weakly simple or non-self-crossing. Since these terms are ...
1k views

### Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
336 views

### Belief propagation for approximate real 3LIN?

In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-...
1k views

### Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
3k views

Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an ...
1k views

### Sorting using a black box

Assume that we want to sort a list $S$ of $n$ real numbers. Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly. How much advantage can we gain using this black box? ...
1k views

### Finding a 5-cycle in a sparse graph efficiently.

(crossposted from MathOverflow) Hi, I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I want to find a 5-cycle in a graph. Actually, what I really ...
596 views

1k views

### Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

In their paper (p. 503) Garey and Johnson remark: ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ......
1k views

### Computing the Cheeger constant: feasible for which classes?

Computing the Cheeger constant of a graph, also known as the isoperimetric constant (because it is essentially a minimum area/volume ratio), is known to be NP-complete. Generally it is approximated. ...
668 views

### How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

Can anyone help me with the following problem? I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K$ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of ...