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
3 votes
0 answers
58 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 ...
Colin McDonagh's user avatar
3 votes
0 answers
164 views

Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
Ben Southworth's user avatar
3 votes
0 answers
135 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 ...
Ilk's user avatar
  • 920
3 votes
0 answers
116 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 ...
Antimony's user avatar
  • 917
3 votes
0 answers
297 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 ...
puneet's user avatar
  • 131
3 votes
0 answers
273 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 ...
stamps's user avatar
  • 33
3 votes
0 answers
98 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 :...
Mathieu Mari's user avatar
3 votes
0 answers
126 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-...
Thatchaphol's user avatar
  • 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 ...
Aaron Rotenberg's user avatar
3 votes
0 answers
119 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=...
GOLD's user avatar
  • 175
3 votes
0 answers
92 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 ...
Joseph Stack's user avatar
  • 1,095
3 votes
0 answers
202 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....
Andras Farago's user avatar
3 votes
0 answers
155 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 ...
user6818's user avatar
  • 281
3 votes
0 answers
320 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 ...
Russell Easterly's user avatar
3 votes
0 answers
162 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 $...
Phylliida's user avatar
  • 1,142
3 votes
0 answers
483 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 ...
In Theory's user avatar
  • 131
3 votes
0 answers
690 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 ...
user1278599's user avatar
3 votes
0 answers
206 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: \...
shortestPath's user avatar
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-...
user1438003's user avatar
3 votes
0 answers
174 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 ...
hbm's user avatar
  • 96
3 votes
0 answers
626 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 ...
Jatin's user avatar
  • 185
3 votes
0 answers
191 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\...
dan_x's user avatar
  • 681
3 votes
0 answers
354 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 ...
chf's user avatar
  • 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. ...
Giuseppe's user avatar
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(...
gilleain's user avatar
  • 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.
Aadith Ramia's user avatar
2 votes
0 answers
41 views

Hardness of Coloring based on a Black-Box Hardness of Independent Set

It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent ...
John's user avatar
  • 412
2 votes
0 answers
103 views

Two disjoint paths with minimum product of weights -NP-completeness

I want to know whether the following problem is NP-complete; Given an undirected graph $G=(V,E)$ with weights on each edge $e\in E$, and two vertices $s,t\in V$, find two disjoint paths $P_1, P_2$ ...
sally's user avatar
  • 21
2 votes
0 answers
67 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 ...
Karagounis Z's user avatar
2 votes
0 answers
117 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?
geeko's user avatar
  • 131
2 votes
0 answers
112 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(...
loplo's user avatar
  • 41
2 votes
0 answers
102 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 ...
Dmytro Taranovsky's user avatar
2 votes
0 answers
70 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 ...
Kirubakaran V K's user avatar
2 votes
0 answers
165 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 ...
Matthieu Latapy's user avatar
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, $...
Yaroslav Bulatov's user avatar
2 votes
0 answers
100 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 ...
delete000's user avatar
  • 828
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 ...
Matthieu Latapy's user avatar
2 votes
0 answers
34 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 ...
Matthieu Latapy's user avatar
2 votes
0 answers
73 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, ...
Chris Grossack's user avatar
2 votes
0 answers
130 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 ...
user1246462's user avatar
2 votes
0 answers
26 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 ...
botsina's user avatar
  • 101
2 votes
0 answers
169 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 $\...
Tacocat's user avatar
  • 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 ...
Giorgio Camerani's user avatar
2 votes
0 answers
84 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 ...
Yuliang Li's user avatar
2 votes
0 answers
58 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 ...
Geoffrey Irving's user avatar
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. ...
f10w's user avatar
  • 241
2 votes
0 answers
144 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). ...
Mengfan Ma's user avatar
2 votes
0 answers
188 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 ...
hqztrue's user avatar
  • 112
2 votes
0 answers
180 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 ...
Tfovid's user avatar
  • 149
2 votes
0 answers
152 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 ...
user3508551's user avatar
  • 1,153