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
5
votes
0answers
60 views

How to find the second smallest cut in a graph?

For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...
1
vote
0answers
39 views

Generalizing PageRank for tripartite graphs

Problem I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...
0
votes
1answer
65 views

Given a partition and an element, find the subset that includes this element

I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
3
votes
1answer
74 views

Algorithm to find $n$ player nash equilibrium

This is the question asked 10 years before. Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years? The game dealing ...
2
votes
1answer
106 views

Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)

I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is $$\exists x \forall y ((y \ge 1 \land y \le ...
4
votes
1answer
247 views

Can we efficiently convert from NFA to smallest equivalent DFA?

Definitions For any automaton $X$, let $L(X)$ denote the language recognized by $X$. For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$. ...
4
votes
0answers
84 views

Minimum spanning tree, but with an unusual objective function

This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem. If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
-1
votes
0answers
48 views

Complexity of recognizing strings in $NPDA$

If an $NPDA$ has $k=poly(n)$ states with branching factor $m$ and the input strings are limited so that stack sizes are $d=poly(n)$ in length what is the best algorithm to parse strings on length $n$ ...
-3
votes
0answers
90 views

The max-min resource assignment problem

I am wondering if there are any results for the following max-min assignment problem: Given n machines C = {C$_1$, C$_2$... C$_n$} with the k-th machine has power C$_k$. There are m tasks T = {T$_1$, ...
4
votes
2answers
157 views

The Dyck Language Correction Problem

Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a ...
2
votes
0answers
83 views

Fastest triangle counting algorithms in dense graphs

One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the ...
2
votes
0answers
64 views

Is there an approximation algorithm for the three-person stable roommates problem? [closed]

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the threesome roommates problem, is NP-...
5
votes
0answers
157 views

Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

This problem came up in my study of digraphs: Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$. Note that $A$...
12
votes
2answers
158 views

Is the exponent in the rectangular matrix multiplication convex?

My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a ...
4
votes
1answer
151 views

Is $GCT$ necessarily a negative result program?

$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
9
votes
1answer
185 views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
10
votes
1answer
331 views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner. We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
4
votes
2answers
197 views

Is there a linear time algorithm for integer multiplication verification?

There is a quadratic randomized algorithm for matrix product verification. Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
0
votes
1answer
64 views

Knapsack problem with dependent weight and profits among the items

I'm working on a problem that may be reduced to the following variant of multiple knapsack problem: Each knapsack has its own valuation function; an item brings different profit and weight to a ...
3
votes
1answer
216 views

An optimization problem

I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$ maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
13
votes
0answers
323 views

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

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 ...
4
votes
1answer
145 views

Minimizing $L_2$ norm of a vector with two distinct entries

Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values. Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\...
1
vote
1answer
104 views

Complexity of a satisfiability problem

I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below. Given $n$ ...
2
votes
1answer
139 views

Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
0
votes
0answers
118 views

Triangle counting using approximate matrix multiplication — suspicious paper

This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper)....
3
votes
0answers
44 views

Counting subsets of bipartite graph part which admit an induced perfect matching

Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
0
votes
0answers
38 views

Maximum resistor with sublinear number of measurements

Consider a set $X = \{x_1, \dots, x_n\}$ of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset $S \subset X$, we can build resistive circuits and measure ...
8
votes
1answer
269 views

Time complexity for a variant of edit distance

This question is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...
2
votes
0answers
97 views

$k$-XOR collision free families

Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies: $\forall i: v_i\in\{0,1\}^{z_{n,k}}$. The bitwise xor ...
8
votes
1answer
311 views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses. Being $s_k=\...
2
votes
0answers
58 views

Can we always find a graph with a given algebraic connectivity?

This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong. I would like to experiment with various spectral properties of graphs, ...
1
vote
0answers
41 views

Dynamic permutation cycle data

Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time? sameCycle($\pi,x,y$): determines ...
1
vote
1answer
155 views

An extension to the student/college admissions Gale-Shapley algorithm

The Gale-Shapley algorithm is an established algorithm that finds an optimal one-to-one match between two groups, each individual of which has a preference for the individuals in the other group (the &...
6
votes
0answers
137 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 ...
2
votes
0answers
118 views

Finding nodes with enough unique ancestors

Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
1
vote
1answer
62 views

Separating DAGs using separators consisting of lists of nodes and all ancestors

Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
1
vote
0answers
37 views

Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
2
votes
0answers
84 views

Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
18
votes
1answer
1k views

Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
4
votes
0answers
81 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
18
votes
0answers
407 views

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Decision Problem Input: An $m$ by $n$ Boolean matrix $M$. Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
0
votes
1answer
81 views

Algorithm to calculate coordinated radio frequencies

I'm stuck on this algorithm problem for a project I'm working on. I can find no relevant documentation, and would very much appreciate any help that can be offered on this! I will try to explain it ...
0
votes
0answers
110 views

Algorithms and approximations for optimal offline binary tree operations

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
5
votes
1answer
78 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
4
votes
0answers
309 views

Deciding whether $2^k+m$ is prime

I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts. Does there exist a deterministic polynomial-...
1
vote
0answers
45 views

Reference request: algorithm meta-analyses

Could you direct me to papers that survey families of algorithms? The ideal paper would focus on a single family of algorithms, would show how the improvements in each algorithm work, and ideally ...
3
votes
1answer
250 views

How can I optimize my brute-force solution to this problem?

I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible). Of course, it ...
3
votes
1answer
131 views

Maximum subarray problem with weights

The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j ...
3
votes
1answer
129 views

Polynomial evaluation at all different points

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
4
votes
0answers
113 views

On solving Planar Circuit SAT

This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...

1
2 3 4 5
34