Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
286
questions with no upvoted or accepted answers
2
votes
0
answers
232
views
Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth
I would like to cite a paper/report/etc that solves the following problem polynomially in $n$:
Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
- 103
2
votes
0
answers
1k
views
Is there a better than brute-force solution to the shortest simple path problem?
Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex ...
- 121
2
votes
0
answers
55
views
Examples of "Sandpile" TSP Instances
This question is closely related to this MO question.
I would like to know, whether any (planar Euclidean) TSP instances are known, that exhibit avalanche effects similar to those ecountered in ...
- 131
2
votes
0
answers
297
views
zero-sum path problem on a digraph
Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the ...
- 509
2
votes
0
answers
610
views
Path finding on graph with state dependent edge costs
I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i....
- 161
2
votes
0
answers
86
views
Max common sub forest on $k$ graphs
Not sure how to phrase this really, but here goes.
Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$.
The problem is to find ...
- 53
2
votes
0
answers
38
views
Nearest Common Ancestor on DFS Tree (with Addition of Leaves in DFS Order) on Pointer Machines
What is the complexity status for the Nearest Common Ancestor Problem on Trees in which the leaves are attached to the tree in DFS order ?
i.e. Suppose one is visiting a tree T in DFS, and at any ...
- 650
2
votes
0
answers
591
views
Shortest non-crossing geometric paths
I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
user7329
2
votes
0
answers
106
views
Claw finding using quantum walk: superposition for Szegedy's framework
Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper:
Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
- 155
2
votes
0
answers
44
views
centralized deterministic Spanner construction with low degree and low stretch
Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
- 33
2
votes
0
answers
183
views
Hardness of approximately counting independent sets with a PRAS, rather than FPRAS
It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least 6....
- 11.2k
2
votes
0
answers
145
views
About the sparsest-cut question
Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph?
(Isn't the set which achieves the Cheeger constant for a ...
- 271
2
votes
0
answers
147
views
How much faster is solving Clique in properly colored graph?
Given a graph $G$ and a proper vertex coloring $C$ with the minimum
numbers of colors, how much faster can a maximum clique be found than
when just $G$ is given?
Additional information doesn't make ...
- 1,955
2
votes
0
answers
102
views
What mathematical models can analyze and optimize such message passing system?
I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message ...
- 121
2
votes
0
answers
151
views
Realization of a bipolar orientation by a mixed graph
Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular ...
- 467
2
votes
0
answers
148
views
Weighted graph as average of many unweighted graphs
I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs.
My idea is that if I consider a weighted graph as ...
- 221
2
votes
0
answers
195
views
What is the name for this special case of the Travelling Salesman involving dynamic edge costs?
This is a modeling / taxonomy question. Is there a name for this type of problem?
I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel ...
- 121
2
votes
0
answers
178
views
Graph partition with objective over intra-partition weights
I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
- 21
2
votes
0
answers
200
views
Eulerian Triangulations
Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree.
I cam across this page http://cs.anu.edu....
- 1,006
2
votes
0
answers
66
views
Hungarian Search and min net-cost-length paths
Consider the Hungarian Search algorithm for max/min weighted bipartite matching. Let G be a bipartite graph weighted by $w:E\rightarrow\mathbb{R}$ and let $M$ be a matching in $G$, let $S$ be a subset ...
- 650
2
votes
0
answers
1k
views
Maximum number of triangles in a constrained delaunay triangulation
I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number ...
- 383
2
votes
0
answers
225
views
Quadratic Binary Optimization formulation of Steiner Tree problem
can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?...
2
votes
0
answers
94
views
Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?
Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so ...
- 21
2
votes
0
answers
233
views
Map points from one plane into another
Given a point on a plane A, I want to be able to map to a corresponding point on plane B. I have a set of N corresponding pairs of reference points between the two planes, however, the overall mapping ...
- 129
2
votes
0
answers
240
views
Initial paper of the Moore Neighborhood algorithm
I don't exactly know if this is the place to ask it, but I'm looking for the original paper of the Moore Neighborhood algorithm. I need to make a reference to it (or whoever came up with it). I can't ...
- 121
2
votes
0
answers
270
views
Algorithm for choosing unique items from a collection of sets of items
I have a number of sets, each containing items with a numerical value and a string.
I want to choose one item out of each set, so that:
1. the strings of the chosen items form a set (i.e. the strings ...
- 153
2
votes
0
answers
510
views
Data set for Degree Constrained MST?
Degree Constrained Minimum Spanning Tree is an NP-hard problem. It differs from Minimum Spanning Tree in that, degree of every vertex should be $\leq$ some degree constrained. This is a well studied ...
user770
1
vote
0
answers
41
views
Max Flow Routing
Let G = (V,E,S,I,T) be a directed flow network with nodes V, edges E with unit capacity, source nodes S $\subseteq$ V, intermediate nodes I $\subseteq$ V, and target nodes T $\subseteq$ V. The problem ...
- 11
1
vote
0
answers
36
views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers.
In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 484
1
vote
0
answers
62
views
Finding a Hamiltonian cycle in a graph if we are guaranteed that there are not many of them in the graph
Problem: Given an undirected simple graph $G=(V,E)$ on $n$ vertices, such that there are not more than $c^n$ ($c<2$) Hamiltonian cycles in $G$, find a Hamiltonian Cycle in $G$ if there exists one.
...
- 11
1
vote
0
answers
51
views
Approximation algorithm for non-bipartite Euclidean matching
What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are ...
- 11
1
vote
0
answers
36
views
Minimum vertex-separators under edge addition
I am trying to prove the following claim.
Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$.
Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
- 95
1
vote
0
answers
100
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.2k
1
vote
0
answers
26
views
Can input-output matrices optimize bidirectional search?
Given a bidirectional search on a weigthed digraph, could a modified input-output matrix guess what nodes are more likely to belong to the shortest path and the search be done through these nodes ...
1
vote
0
answers
53
views
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
- 11
1
vote
0
answers
106
views
Efficient enumeration of connected functional digraphs (up to isomorphism)
Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
1
vote
0
answers
59
views
Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?
The shortest $k$-edge disjoint paths problem is defined as follows:
Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Find (if exist) $k$-pairwise ...
- 141
1
vote
0
answers
171
views
Cheapest Insertion is $2$-approximation for TSP
Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
- 11
1
vote
0
answers
108
views
A reduction from the maximum $k$-closure problem to the clique problem
Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
- 111
1
vote
0
answers
51
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
user53330
1
vote
0
answers
69
views
Prune length distribution of random binary tree
Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
1
vote
0
answers
37
views
Latest results on the k-stacker crane problem?
I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the ...
- 11
1
vote
0
answers
56
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]\...
- 111
1
vote
0
answers
38
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 ...
- 291
1
vote
0
answers
43
views
granularity of bidirectional breadth-first search
I tried posting this on stack overflow and it got no takers, decided to cross post here:
One thing that I've never seen discussed about bidirectional breadth-first-search (which I'll abbreviate as ...
- 111
1
vote
0
answers
41
views
Efficient algorithm for finding segregators in a directed acyclic graph
Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
- 633
1
vote
0
answers
82
views
Are the intermediary sets in maximum cardinality search optimal in some way?
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
- 1,921
1
vote
0
answers
52
views
Minimum rank graph cut
Consider the following problem:
Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle.
Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
- 11.2k
1
vote
0
answers
115
views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
user17918
1
vote
0
answers
63
views
Directed Acyclic Graph partition into minimum subgraphs with a constraint
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
- 111