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

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
7
votes
2answers
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,...
15
votes
5answers
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 ...
12
votes
4answers
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 ...
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
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 ...
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
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 ...
6
votes
2answers
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 ...
13
votes
0answers
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 ...
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
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 ...
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
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 ...
4
votes
6answers
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 ...
12
votes
2answers
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 ...
3
votes
1answer
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 ...
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
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 ...
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
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 ...
0
votes
1answer
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 ...
17
votes
2answers
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 ...
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
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. ...
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
696 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
103 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
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 ...
1
vote
0answers
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'}$ ...
7
votes
0answers
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 ...
3
votes
0answers
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(...
2
votes
1answer
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 ...
7
votes
2answers
290 views

Is it easy to “fit a wrapped chain in a graph”?

Given a directed graph $G=(V,A)$ with a unique source node $s$ (a node without incoming edges) and a unique sink node $t$ (a node without outgoing edges). Given a sequence of variables $SEQ = (x_{i_1}...
7
votes
0answers
381 views

Embedded dynamic programming (and planar subgraph isomorphism)

In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
4
votes
2answers
337 views

Shortest paths with structured dependence on earlier path

Perhaps this problem has been studied under a different guise. If so, I'd appreciate any pointers or terms that could help my search for related work. Suppose we have an undirected simple graph $G=(V,...
8
votes
3answers
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 ...
12
votes
3answers
806 views

NP-hard problems on cographs

This question is similar to NP-hard problems on trees: There is a large number of NP-complete problems that are tractable on cographs. Are there any known problems that remain NP-complete when ...
6
votes
2answers
727 views

Complexity of transforming a balanced bipartite graph into regular graph?

I'm studying certain graph editing problems and I'd like to determine the complexity of this problem: Input: Balanced bipartite graph $G(A \bigcup B, E)$, $|A|=|B|=n$, integer $k$ Problem: Is there $...
9
votes
1answer
3k views

What's the approximation factor of this Max k-Cut approximation?

I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows. Input is a graph G = ...
4
votes
2answers
328 views

Find optimal room from which to visit all other rooms in a rectangular floorplan

Suppose we have an orthogonal polygon with holes (all walls are axis-parallel). All vertices can be on integer coordinates, if that helps. Partition the polygon into rectangular rooms. I would like ...
12
votes
2answers
483 views

MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, ...
7
votes
1answer
742 views

Approximating transitive reduction of a transitive closure of a dag

Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...
15
votes
3answers
896 views

Super Mario Flows in NP?

One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
9
votes
2answers
3k views

Testing/Identifying a Topological Sorting

You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...