Tagged Questions

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

53 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 ...
94 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. ...
68 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 ...
56 views

Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
56 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 ...
250 views

244 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 ...
87 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. http://math....
84 views

Efficient algorithms for counting $k$-clique subgraphs

Given a graph $G$ with $n >> k$ vertices, what are the fastest algorithms known to count the number of induced subgraphs in $G$ that are $k$-cliques? Are there algorithms that can do better ...
52 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 , ...
184 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$,...
127 views

182 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 ...
167 views

164 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 ...