# Questions tagged [ds.algorithms]

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

466 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
199 views

### Complexity of checking if AB intersects C

Let $A,B,C$ be subsets of a nonabelian group $G$, and assume we know the structure of $G$ "fairly well" (e.g., $G = S_n$ or $A_n$). Assume that group operations take $O(1)$ time. Is it ...
487 views

### Nuts and Bolts problem: Simpler $o(n^2)$ algorithm

In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-...
342 views

### Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph

Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal ...
177 views

### Is the dominating set problem constant-factor-approximable in undirected path graphs?

I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class. A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
366 views

### Efficiently approximating derivative of a well-behaved function

I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
171 views

### Can one find good distance-2-separators in planar graphs?

It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph. However, it ...
195 views

### what is the best heuristic to solve 3AP with Euclidean costs?

As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian ...
113 views

### Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes: Is there an algorithm that enumerates the ...
2k views

### Fast Hamiltonian Cycle finding Algorithm

We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there ... 438 views

### Type inference with subtype constraints and polymorphism using Trifonov and Smith's constraint maps

Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable ...
168 views

### Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
192 views

### Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
114 views

### Consequence of Decision Tree Complexity of $k$-SUM Problem

Ezra and Sharir showed the $O(n^2\log^2 n)$ linear decision tree complexity for $k$-SUM problem , which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al . It is known that $k$-... 466 views

### Worst-case computational complexity of solving Diophantine equation

Manders and Adleman proved that the following decision problem is NP-complete: Given integers $a,b,c>0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y>0$? The ...
266 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 ...
277 views

### Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
1k views

### Is there a linear-time algorithm for max flow on dags

What is the fastest known algorithm for max flow on dags? Can there be a linear-time algorithm running in time $O(|V|+|E|)$? Input: a weighted dag $G=(V,E,w)$ where $E$ is given as an edge list $E$ ...
68 views

### Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
1k views

### Best algorithm for inversion of symmetric positive-definite matrices

As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a ...
225 views

### Is there a programming language where any arbitrary recursive function can be fused?

Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
374 views

### Minimum length cuts needed to remove holes in a polygon

Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary ...
205 views

### Is the following "Occam's razor" decision problem a member of P?

While thinking about natural language processing, I came up with the following NP problem: OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ... 120 views

### Is there any known result for 1-median problem with negative weights in Euclidean space?

Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$ such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the weight of $v_i$, which may be positive or negative. ...
155 views

### Lower bound for the maximal vectors problem

I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
3k views

### Time complexity of standard semidefinite programming solvers

I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs. (I am not interested in algorithms like multiplicative weights updates method.)
963 views

### Biconnected components of a directed graph?

I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
496 views

### An algorithm to compute the number of paths of length at most k

So I had to answer the following question: Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
230 views

### Minimum weight expander

Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
250 views

### How quickly can we find an arbitrary digit in multiplication?

In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication. We may first consider previous results. Finding the least significant digits is ...
189 views

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)... 7 votes 0 answers 199 views ### Tree search guided by a probabilistic oracle I'm trying to find a solution for the following problem. I have a tree$T$of branching factor$b$and depth$d$. For the moment, I only care about the case where I restrict$b=2$, but I would be ... 7 votes 0 answers 239 views ### Can we achieve a better kernel for the Vertex Cover problem on planar graphs? We have known how to get a$2k$kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is easy ... 7 votes 0 answers 1k views ### Sparse graphs versus dense graphs I am curious if there are graphs problems for which either - we know that time and/or space complexity is independent of graph sparsity we do not know whether or not graph sparsity can be exploited ... 7 votes 0 answers 831 views ### Approximation results for 3-partition The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the$m$subsets each have at most three elements and a sum of not ... 7 votes 0 answers 191 views ### Scaling Algorithms for the Minimum Spanning Tree Problem? In his paper "Scaling Algorithms for Network Problems", Harold Gabow details several algorithms for graph problems that work using scaling, iteratively refining a candidate answer by beginning with a ... 7 votes 0 answers 100 views ### Ref - Implicit selection made quick? Given a matrix of size$n\times n$with numbers, where every row is sorted, one can compute the$k$th smallest element in$O(n \log^2 n)$time by simulating (implicitly) quick-select on this matrix (... 7 votes 0 answers 160 views ### log(OPT) approximation for directed balanced vertex separator Leighton, Rao presented an$O(\log n)$approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of ... 7 votes 0 answers 353 views ### Good MCMC methods for exploring the space of independent sets Let$G$be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge ... 7 votes 0 answers 392 views ### Embedded dynamic programming (and planar subgraph isomorphism) In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ... 7 votes 0 answers 166 views ### Finding the set of paths of smallest cumulated length that cover a given set of patterns First of all, sorry for this long and maybe not very informative title... Context: Let$G=(V,E)$be a directed graph, let$v_0 \in V$be the initial node of paths that I will consider in the graph. ... 6 votes 0 answers 165 views ### Computing and maintaining the minimum of a set$S$of integers while allowing updates on$S$This question is about computing and maintaining the minimum of a set$S$of integers while allowing updates on$S$. The computation model we are considering is the unit-cost RAM machine with linear ... 6 votes 0 answers 198 views ### Bottleneck$k$-link path in a complete DAG Let$G$be a complete DAG: It has vertices$v_1,\ldots,v_n$, and$v_iv_j$is an edge if and only if$i<j$. Let$w(i,j)$be the weight of the edge$v_iv_j$. The weight has the property that$w(i,j)&...
138 views

I hope this is a suitable place to ask this question. An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
169 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 ...
118 views

### Lower bounds for randomized frequency estimation algorithms

Consider a stream of elements $s_1s_2\ldots s_N$. A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"? It ...
148 views

### Is higher-order unification decidable for terms without abstractions within applications?

Consider the problem of higher order unification - that is, finding a substitution for the equation a = b, where a and ...