People who code: we want your input. Take the Survey

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
305 views

### How hard is counting the number of vertex covers after a small perturbation?

Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely,...
879 views

### References for Modular Decomposition

What are good papers/books to better understand the power of Modular Decomposition and its properties? I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
799 views

### What is the most important notion of sparsity for the design of efficient graph algorithms?

There are several competing notions of a "sparse graph". For instance, a surface-embeddable graph could be considered sparse. Or a graph with bounded edge density. Or a graph with high girth. A ...
3k views

### Program for computing Tree decomposition of a graph

Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
4k views

### Finding the longest path between two nodes in a bidirectional unweighted graph

I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph. The path must not have repeated vertices (otherwise the path would be infinite of ...
496 views

### The existence of planar distance preserver?

Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property $$d_H(u,v) = d_G(u,v)$$ for all nodes ...
384 views

### What is the name of this type of directed graph problem?

Take a directed graph $G$ where the edges are decorated with a a natural number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is ...
243 views

### Restricted Reachability Problem

Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
524 views

### What algorithm on a PRAM computes the connected components of a graph with least time complexity?

The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on ...
962 views

### What is the currently best known algorithm for the transportation problem?

Consider the well known transportation problem: There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs. Every node has a integer supply or demand, and the arcs have integer costs, used ...
195 views

### Four color theorem and map pre-simplification of faces with less than 5 edges

It is already known that in searching for a solution of the four color problem, regular maps can be pre-simplified by removing all faces with less than four edges. This is described for example in the ...
306 views

### Is there a local variant of TSP?

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take. It's likely NP-hard, I was just wondering if ...
290 views

### Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps? For rectangular maps, for example, I intend maps that are made from overlapping ...
149 views

### A better way to cluster items

I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as ...
516 views

### Graph planar drawing, with each edge's length is known

Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not. Further assume that this is a graph that can be embedded ...
3k views

### Algorithm for finding the largest subgraph without a directed triangle

I would like to find the largest set of vertices in a directed graph. This set should not contain a cycle with exactly three vertices. Cycles with less vertices aren't possible with the given graphs; ...
8k views

### What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
871 views

### Minimum Flip Connectivity Problem

I formulated the following problem today while playing with my GPS. Here it is : Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of ...
743 views

### Is feedback vertex set problem is solvable in polynomial time for some special graph

Feedback vertex set (FVS) problem is NP-complete for both undirected and directed graphs, and it is NP-complete even for bipartite graphs and tournaments. Is there any special family of graphs other ...
473 views

### Euclidean-squared max-cut in low dimensions

Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
348 views

### Finding common label sequences in a directed acyclic graph

I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the ...
1k views

### Path of exact cost in edge labelled DAG?

Given edge labelled directed acyclic graph with edge labels $w_i \in \mathbb{N}$ the cost of a path is the sum of the labels. The problem is: Find a path from $s$ to $t$ with cost $a$. I suppose ...
411 views

### Graph Connectivity

Given a graph $G = (V, E)$, I need to determine: $k$, the graph connectivity. Which are those $k$ vertices to remove to make $G$ disconnected. Questions Which is the complexity of such ...
330 views

### Number of Vertex Covers: when it is polynomial and when it is superpolynomial

The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to ...
356 views

### Construction of graph embeddings with non-intersecting edges

I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this ...
812 views

### graph coloring with 3 colors

I'm searching for an algorithm that can calculate a suboptimal solution for: color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the ...
510 views

### Parameterized complexity of graph intersection number

What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)? It has long been known to ...
426 views

### Combinatorial Independent set Algorithms for sub-classes of perfect graphs

As an extension to the question posed recently by Bulatov, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent ...
301 views

### Determining Graph Hulls

Consider the following undirected unweighted graph: The green nodes separate the graph from the "external environment". Let's call them the graph hull. Now, a graph may have several hulls. ...
2k views

### Reference for fast algorithm for bottleneck shortest paths

I am looking for a good reference for bottleneck shortest paths. Specifically, given vertices s and t in an undirected graph with edge weights, you want the shortest path from s to t, where the ...
696 views

288 views

### An image coloring problem

I have a large collection of microscopy images of cell cultures. Each image consists of $10^{10} \times 10^{10}$ pixels. These images have been "segmented", meaning that their pixels have been ...
553 views

### Minimum Weight Disconnected Subgraph and “Opposite” problems

Given a graph $G = (V,E)$ and a vertex weight $z_v$ for each $v \in V$, find an (EDIT) induced subgraph $G' = (V', E')$ with minimum weight $z_{G'}=\sum_{v' \in V'} z_{v'}$ ...
312 views

### Good MCMC methods for exploring the space of independent sets

Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge ...
118 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(...
389 views

### ATSP with direction restrictions

I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified ...
290 views

533 views

### Route existence between n pairs of nodes

Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple ...