Skip to main content

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

290 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers
188 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_{...
Pawan Aurora's user avatar
2 votes
0 answers
53 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$...
hnewton 's user avatar
2 votes
0 answers
117 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 ...
jcai's user avatar
  • 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 ...
joro's user avatar
  • 1,955
2 votes
0 answers
219 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 ...
Mohemnist's user avatar
  • 230
2 votes
0 answers
268 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-...
cs_student_273's user avatar
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 ...
Benno's user avatar
  • 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 ...
Manfred Weis's user avatar
2 votes
0 answers
304 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 ...
wei wang's user avatar
  • 519
2 votes
0 answers
632 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....
Stanley F.'s user avatar
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 ...
user1441057's user avatar
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 ...
XORwell's user avatar
  • 650
2 votes
0 answers
622 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 ...
user avatar
2 votes
0 answers
107 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 ...
Fleeep's user avatar
  • 155
2 votes
0 answers
45 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. ...
SSS's user avatar
  • 33
2 votes
0 answers
148 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 ...
joro's user avatar
  • 1,955
2 votes
0 answers
103 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 ...
DuckQueen's user avatar
  • 121
2 votes
0 answers
155 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 ...
seteropere's user avatar
2 votes
0 answers
149 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 ...
linello's user avatar
  • 221
2 votes
0 answers
199 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 ...
Aaron Fi's user avatar
  • 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 ...
user136011's user avatar
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....
Dibyayan's user avatar
  • 1,016
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 ...
XORwell's user avatar
  • 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 ...
zaloo's user avatar
  • 393
2 votes
0 answers
226 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?...
Davide Venturelli's user avatar
2 votes
0 answers
95 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 ...
Antonio's user avatar
  • 21
2 votes
0 answers
255 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 ...
Jason's user avatar
  • 129
2 votes
0 answers
243 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 ...
Olivier_s_j's user avatar
2 votes
0 answers
271 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 ...
Jonatan Kallus's user avatar
2 votes
0 answers
514 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 ...
user avatar
1 vote
0 answers
68 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
user72110's user avatar
1 vote
0 answers
32 views

How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
SZH's user avatar
  • 11
1 vote
0 answers
48 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 ...
sripurva's user avatar
1 vote
0 answers
58 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 ...
Naysh's user avatar
  • 686
1 vote
0 answers
67 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. ...
jamal_asif's user avatar
1 vote
0 answers
56 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 ...
Sandip's user avatar
  • 11
1 vote
0 answers
40 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), ...
BBK's user avatar
  • 103
1 vote
0 answers
104 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 ...
Andras Farago's user avatar
1 vote
0 answers
89 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 ...
Julien Codsi's user avatar
1 vote
0 answers
116 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 ...
Antonio E. Porreca's user avatar
1 vote
0 answers
72 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 ...
advocateofnone's user avatar
1 vote
0 answers
223 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 ...
Ioana Roman's user avatar
1 vote
0 answers
140 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 ...
dvitek's user avatar
  • 111
1 vote
0 answers
57 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 $\...
user avatar
1 vote
0 answers
81 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 ...
user152789811's user avatar
1 vote
0 answers
40 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 ...
Kien Hunh's user avatar
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]\...
hldev's user avatar
  • 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 ...
dohmatob's user avatar
  • 291
1 vote
0 answers
46 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 ...
Mark VY's user avatar
  • 111
1 vote
0 answers
42 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$ ...
exfret's user avatar
  • 653