Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
9
votes
4answers
13k views

What is the computational complexity of "solving" chess?

The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work ...
2
votes
3answers
374 views

Heuristics for graph bisection

i'm trying to find an algorithm that will divide my graph in 2 parts by telling me what connections should be broken but the 2 parts should contain about the same number of nodes its for a practical ...
17
votes
1answer
554 views

Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
9
votes
2answers
551 views

Does there exist a data structure for quick list manipulation and order queries?

We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$. Each element from $N$ appears in a single list in $L$. I am looking for a data structure which can perform the ...
3
votes
4answers
3k views

Finding cliques in a big graph

I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007. The cliques ...
7
votes
1answer
169 views

Using MSOL for solving BIDS problem

From "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al) we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear ...
4
votes
1answer
516 views

Does this graph problem have a formal name?

Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through ...
4
votes
0answers
265 views

Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
11
votes
3answers
1k views

Regular Graphs and Isomorphism

I would like to ask whether there is an already published result on that: We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
15
votes
1answer
831 views

Modular Decomposition and Clique-width

I am trying to understand some concepts about Modular decomposition and Clique-width graphs. In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-...
4
votes
1answer
247 views

How to determine if a labelled digraph contains a cycle with given labels?

Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at ...
3
votes
1answer
340 views

Are there good implementations for easy subclasses of NP-hard graph problems

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
2
votes
1answer
264 views

Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
1
vote
1answer
226 views

Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST

I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum ...
13
votes
1answer
757 views

Largest common subgraph of two maximal planar graphs

Consider the following problem - Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and ...
7
votes
2answers
306 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,...
15
votes
5answers
882 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 ...
13
votes
4answers
808 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 ...
22
votes
5answers
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 ...
5
votes
4answers
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 ...
14
votes
2answers
501 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 ...
16
votes
1answer
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 ...
6
votes
0answers
244 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 ...
6
votes
2answers
526 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 ...
13
votes
0answers
980 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 ...
0
votes
1answer
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 ...
7
votes
2answers
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 ...
5
votes
1answer
291 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 ...
0
votes
0answers
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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; ...
25
votes
5answers
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 ...
25
votes
5answers
897 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 ...
4
votes
6answers
768 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 ...
12
votes
2answers
474 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 ...
3
votes
1answer
350 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 ...
3
votes
2answers
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 ...
2
votes
2answers
412 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 ...
1
vote
1answer
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 ...
5
votes
2answers
366 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 ...
0
votes
1answer
817 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 ...
17
votes
2answers
512 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 ...
7
votes
1answer
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 ...
7
votes
1answer
303 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. ...
12
votes
2answers
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 ...
17
votes
2answers
714 views

Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations? $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$ $link(G,...
5
votes
2answers
290 views

Generation of unlabeled acyclic digraphs

I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order. (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.) Thanks Edit: ...
5
votes
0answers
104 views

Quantized Unbounded Flow

I am interested in the following flow problem, since it turns out to be equivalent to a more general problem. INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $...
7
votes
1answer
289 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 ...
1
vote
0answers
560 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'}$ ...