Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
286
questions with no upvoted or accepted answers
3
votes
0
answers
131
views
Graph problems in P with unknown lower bounds
I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes:
problems, where we know of ...
- 841
3
votes
0
answers
103
views
Incremental PDA emptiness testing?
Is there anything known about the problem of incremental emptiness testing for a pushdown automata?
Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
- 917
3
votes
0
answers
261
views
How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city
Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints.
Salesman can go to a different city only on weekends, all ...
- 131
3
votes
0
answers
242
views
Enumerating Minimal (a,b) vertex separators in a DAG
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.
$S$ is a ...
- 33
3
votes
0
answers
92
views
Algorithms for Maximum weight connected subgraph in planar graphs
I wonder what is known about the two following maximisation problems.
Maximum weight connected subgraph :
Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$
Output :...
- 475
3
votes
0
answers
120
views
Graph-related applications of the fast Fourier transform (and other algebraic algorithms)
The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).
However, while the fast Fourier transform algorithm implies several other near-...
- 1,130
3
votes
0
answers
152
views
Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem
Suppose we are given a standard first-order unification problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal ...
- 236
3
votes
0
answers
117
views
Restricted k-set cover is in NL or L
Restricted $k$-set cover:
Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.
Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\},
i_1=min(S_1),i_2=...
- 175
3
votes
1
answer
380
views
Can Lexicographic BFS be implemented in logspace?
Input: Given graph $G=(V,E)$ vertex labeling in some order
Output: Change the labeling of vertices's such that
labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
- 31
3
votes
0
answers
91
views
Maximum weight triangles in dense graphs
There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs.
Several of these ...
- 1,085
3
votes
0
answers
304
views
Independent Sets that are Odd Covers
I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
- 519
3
votes
0
answers
161
views
Multi-Agent Pathfinding
Quoting from Wang and Botea 2011:
An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $...
- 1,092
3
votes
0
answers
480
views
Broadcasting in node-weighted graphs
Given an undirected graph $G=(V,E)$ with non-negative node-weights $\text{w}(v)$, $v \in V$,
I want to find a spanning tree $T$ of $G$ with minimum "cost"
$\text{w}(T) = \sum_{v\in V} \deg_T(v)\cdot ...
- 131
3
votes
0
answers
644
views
Is there a tight lower bound on the complexity of SSSP on a graph?
I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
- 31
3
votes
0
answers
202
views
Randomized rounding on a graph
Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:
\...
- 181
3
votes
0
answers
75
views
Load-balancing; Alternate methods of keeping track of nodes?
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.
One popular method uses virtual-...
- 131
3
votes
0
answers
170
views
Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints
Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of ...
- 96
3
votes
0
answers
625
views
K-shortest path in large sparse graph
I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of ...
- 175
3
votes
0
answers
190
views
Separation Oracle for Inverse Bipartite Matching Polytope
The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that
$${\mathbf y}^* = \arg\...
- 671
3
votes
0
answers
352
views
Recursive parallel topological sorting in linear time
While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
- 131
3
votes
0
answers
361
views
Connected Components over Graph with "colored" edges.
We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. ...
- 31
3
votes
0
answers
120
views
Are local canonical labellings of a graph ever a subsequence of the global canonical labelling?
So a canonical labelling of a graph G is a function CL(G) that maps each vertex to a numerical label. Sorry if my definitions are a bit obvious or clumsy, by the way. For every isomorphic graph G', CL(...
- 141
3
votes
1
answer
2k
views
Finding the nearest node to a given set of nodes in a graph
I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.
- 139
2
votes
0
answers
64
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 597
2
votes
0
answers
84
views
Does GHC use graph reduction?
I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
- 131
2
votes
0
answers
99
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
2
votes
0
answers
85
views
Finding Hamilton cycles in random graphs
For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?
If this is an open problem, I will also accept an empirically ...
- 2,422
2
votes
0
answers
60
views
Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?
Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions?
No edge touches vertices other than its end vertices.
At any ...
2
votes
0
answers
141
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
- 693
2
votes
0
answers
97
views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
- 4,661
2
votes
0
answers
99
views
Graph recovery from pairwise-common neighborhoods
Define the common neighborhood of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the pairwise-common ...
- 778
2
votes
0
answers
87
views
Dynamic connectivity with known history, for maximal connected component span
Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
- 693
2
votes
0
answers
33
views
Pagerank update upon vertex removal
Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges.
How to efficiently compute the Pagerank of remaining vertices in the ...
- 693
2
votes
0
answers
70
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, ...
- 121
2
votes
0
answers
128
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 ...
- 87
2
votes
0
answers
21
views
Power of Hyperedge Replacement Grammars (HRGs)
Can HRGs generate languages which equal or include the following graph languages:
All (bipartite) graphs of bounded degree
All (bipartite) planar graphs of bounded degree
All (bipartite) planar ...
- 101
2
votes
0
answers
168
views
Complexity of Edge Coloring Regular Graphs With Large Degrees
There is an interesting series of papers on edge colorability / $1$-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree $\...
- 21
2
votes
0
answers
53
views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
- 6,715
2
votes
0
answers
83
views
Variation of edge-disjoint spanning trees
In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing ...
- 41
2
votes
0
answers
57
views
Efficient game traversal of a DAG of 3-colorings
Let $X$ be a set of size $n$. Consider a game played on board $X$ by two players black and white. Starting with the empty board, each player chooses an empty spot to place a stone. Black moves ...
- 3,243
2
votes
0
answers
89
views
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
I have encountered an interesting problem that I couldn't find any references to solve:
Determine the smallest subset of nodes that
need to be removed from an undirected graph to make it a tree.
...
- 241
2
votes
0
answers
123
views
Common techniques for the acyclic orientation problem under some special constraint?
An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
- 451
2
votes
0
answers
187
views
Shortest s-t path when is allowed to ignore k weights
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
- 112
2
votes
0
answers
178
views
Crime prevention using graph theory and machine learning
I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
- 149
2
votes
0
answers
145
views
Counting the maximum number of paths of length $n$ that differ in at least $k$ edges
What is known about the complexity of solving (or approximately solving) the following problem?
INPUT: Graph $G=(V,E)$ and constants $L$ and $K$.
OUTPUT: The maximum size of any set $S$ of simple ...
- 897
2
votes
0
answers
180
views
A variant of the Maximum Weight Clique problem
I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
- 251
2
votes
0
answers
52
views
Min cut problem on unbalanced partitions for planar graphs with unit capacity edges
The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
- 21
2
votes
0
answers
109
views
Unbalanced connected partition
Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
- 121
2
votes
0
answers
69
views
Complexity consequence of logarithmic boolean width of co-bounded degree graphs?
The paper On graph classes with logarithmic
boolean-width claims that the
boolean width of co-k-degenerate graphs is at most $k\log{n}$
and a lot of graph vertex partition problems can be solved in
...
- 1,955
2
votes
0
answers
215
views
Approximating the Radius of a (Dense) Graph
For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.
A $(1+\epsilon)$-approximating of APSP for a ...
- 230