Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

2,547 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
37 votes
0 answers
585 views

Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ ...
user avatar
  • 371
28 votes
0 answers
691 views

Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
user avatar
23 votes
1 answer
1k views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
user avatar
  • 339
22 votes
0 answers
512 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
user avatar
  • 321
18 votes
0 answers
437 views

Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
user avatar
  • 306
16 votes
2 answers
672 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
user avatar
  • 261
13 votes
0 answers
411 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Consider the following problem: Input: integers $n > m > k$; $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$; $n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$). Let $X_1,\dots,X_n$ be $n$ ...
user avatar
  • 231
13 votes
0 answers
651 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
user avatar
  • 141k
12 votes
0 answers
814 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
user avatar
  • 221
12 votes
0 answers
799 views

Fast algorithm for max-convolution with concave functions?

I'm interested in a discrete max-convolution problem, which is to compute $$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$ for all values $c=0, \ldots, C$, where $x=(...
user avatar
  • 221
11 votes
0 answers
185 views

Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
user avatar
11 votes
0 answers
189 views

Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?

It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
user avatar
11 votes
0 answers
360 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
user avatar
  • 1,914
11 votes
0 answers
2k views

Alternatives to SVD for rank factorization

I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \...
user avatar
11 votes
1 answer
4k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
user avatar
10 votes
1 answer
415 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
user avatar
9 votes
1 answer
1k views

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
user avatar
  • 261
8 votes
0 answers
379 views

Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
user avatar
  • 111
8 votes
2 answers
357 views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
user avatar
8 votes
0 answers
217 views

What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
user avatar
  • 343
8 votes
0 answers
203 views

Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...
user avatar
8 votes
0 answers
963 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
user avatar
  • 209
8 votes
0 answers
2k views

Area of the union of rectangles anchored on the x-axis

I am trying to solve the following computational geometry problem. Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
user avatar
  • 3,149
8 votes
0 answers
1k views

Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)

If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem? (...
user avatar
8 votes
0 answers
200 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
user avatar
  • 81
8 votes
1 answer
142 views

Find all the special graphs which can reduced to the shortest paths graph

I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
user avatar
  • 237
8 votes
1 answer
1k views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
user avatar
  • 339
7 votes
0 answers
295 views

Shortest path in directed graphs with no more than $\log \log n $ negative edges

Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
user avatar
  • 55
7 votes
1 answer
260 views

Polynomial time algorithm for finding a maximal monotone subset

Input: Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$. ...
user avatar
  • 121
7 votes
0 answers
237 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
user avatar
  • 101
7 votes
0 answers
417 views

Algorithms to generate random nowhere-neat rectangulation?

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
user avatar
7 votes
0 answers
201 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
user avatar
7 votes
0 answers
1k views

What is the intuition behind Heap's Algorithm?

I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set. What I can't understand is why if n is even the letter swapped is i and when n is odd the ...
user avatar
  • 223
7 votes
0 answers
371 views

How to efficiently divide a grid with some predefined sub-rectangles?

Given an $M$x$N$ grid with some predefined sub-rectangles. How to divide the grid into a set of sub-rectangles, which contains the predefined sub-rectangles, so that its the number of elements is ...
user avatar
7 votes
0 answers
293 views

What's the complexity of solving a packing LP?

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in ...
user avatar
7 votes
0 answers
202 views

Computing the "at least k friends in common" graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
user avatar
  • 2,209
7 votes
0 answers
1k views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
user avatar
  • 458
7 votes
0 answers
467 views

How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
user avatar
  • 9,209
7 votes
1 answer
677 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
user avatar
7 votes
0 answers
1k views

What machine learning method for diabetes prediction SW?

I'm thinking of an application for diabetics, that, given previous values of blood glucose and insulin dosage, predicts the glucose level for the next few hours. I know a few things about neural ...
user avatar
7 votes
0 answers
166 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
user avatar
7 votes
0 answers
356 views

Worst-case sparse graphs for Hopcroft-Karp Algorithm

Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
user avatar
7 votes
0 answers
186 views

What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
user avatar
  • 261
7 votes
1 answer
263 views

Building cycle in rectangle

I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle. For example: $w = 5\\h=3$ $n = 12\\k = 6$ I have already found out that I need at least $...
user avatar
  • 83
7 votes
1 answer
1k views

Find maximum in array without comparisons between elements

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: ...
user avatar
  • 201
7 votes
1 answer
941 views

Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
user avatar
6 votes
0 answers
639 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
user avatar
6 votes
0 answers
85 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
user avatar
6 votes
0 answers
538 views

What could we say about that conjecture that yields P != NP?

Let $F$ be the set of all Boolean formulae. We say that a Boolean formula $\varphi$ is positive (=monotone) if $\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
user avatar
  • 151
6 votes
0 answers
115 views

Placing a tripod in a plane such that it partition a given set of points (with pic)

I would appreciate if anyone could help me with the following problem: Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
user avatar

1
2 3 4 5
51