A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
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
287 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
538 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
283 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
387 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
286 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
374 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
327 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
525 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
756 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
675 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 $...
6
votes
1answer
2k 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 another one advance approximation algorithms are available here. The Max k-Cut problem is defined as follow: Assume we ...
4
votes
2answers
322 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
439 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
701 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
863 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 ...
8
votes
2answers
2k 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 ...
-4
votes
1answer
858 views

Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
2
votes
1answer
232 views

Searching for name of equivalence property in hamiltonian paths

This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up. Given a hamiltonian path, any subpath ...
11
votes
3answers
3k views

Number of reachable vertices in DAG for every vertex

Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every ...
1
vote
1answer
115 views

Is any related work to this m-trails problem ?

Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following: Given a graph $G=(V,E)$ with its path set ...
22
votes
7answers
2k views

Finding twin vertices in graphs

Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be ...
0
votes
2answers
1k views

Finding minimum spanning 1-tree

We are considering a connected weighted graph G. 1-tree is a tree with one extra edge added (so it contains exactly one cycle). The task is to find minimum spanning 1-tree of G. I was thinking of ...
10
votes
1answer
498 views

Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific ...
6
votes
2answers
978 views

Finding maximum weight arborescence in an edge-weighted DAG

Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$. When all edge weights are positive then the required ...
14
votes
2answers
2k views

Generalization of the Hungarian algorithm to general undirected graphs?

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...
1
vote
0answers
312 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
9
votes
3answers
734 views

How can I randomly generate bounded height spanning trees?

For a project that I am working on, I should generate random spanning trees with bounded height. Basically I do the following: 1) Generate a spanning tree 2) Check the feasibility, if feasible keep ...
19
votes
2answers
743 views

maintaining a balanced spanning tree of a growing undirected graph

I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph. I have an undirected graph that starts as a single node, the "root". At each ...
2
votes
0answers
486 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 ...
21
votes
2answers
943 views

Finding a 5-cycle in a sparse graph efficiently.

(crossposted from MathOverflow) Hi, I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I want to find a 5-cycle in a graph. Actually, what I really ...
25
votes
3answers
965 views

Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph). But what ...
4
votes
3answers
472 views

Is Degrees Of Separation NP Complete?

I'm doing a bit of research on doing social analysis between so called "hub" people. Basically what I want to try to do is determine the shortest paths between two individuals. The problem is that ...
1
vote
1answer
2k views

Algorithm for Longest Path in Undirected Weighted Graph [closed]

EDIT Dec 14th 2010 The algorithm is not correct: it's not the case that it always returns the optimal $W$. While reasoning on this and other similar questions, I've sketched an algorithm that, given ...
8
votes
2answers
472 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
5
votes
1answer
1k views

Max Non-overlapping Path in Weighted Graph

I have a sparse weighted graph, and I want to find the longest path from a given vertex to any other vertex which does not go through the same vertex twice. You can think of it as, I am here, and I ...
2
votes
1answer
229 views

Weighted cycles in weighted line graphs

Assume a planar graph G, and all its vertices have degree at most 4. Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following ...
12
votes
1answer
278 views

Typical hardness of tree decomposition?

Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks. Is anything known about hardness of tree decomposition of a "typical" instance of ...
5
votes
2answers
791 views

For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

I have asked the question at Math SE and at SO, but I can't seem to get the answer I want. So I paraphrase the question and it here. In a planar graph $G$, one can easily find all the cycle basis by ...
9
votes
1answer
348 views

Is the backup problem NP-complete?

Is the following decision problem NP-complete: Let $G$ be an undirected graph and $b \le c$ two integers. Is it possible to select for every vertex of $G$ exactly $b$ different neighbors ...
14
votes
2answers
2k views

Number of mincuts of a graph without using Karger's algorithm

We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$. I was wondering if we could ...
9
votes
3answers
856 views

Tree decomposition for planar graphs

First asked on math.SE with no replies. Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition? What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
1
vote
1answer
1k views

Kernighan–Lin algorithm and multiple gain functions

I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions. Is there some technique to combine gain functions in one ...
3
votes
1answer
2k views

Tarjan Strongly Connected Components Question [closed]

Below is Tarjan's SCC algorithm as described in wikipedia. Input: Graph G = (V, E) ...
20
votes
5answers
1k views

Deterministic Parallel algorithm for perfect matching in general graphs?

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
11
votes
2answers
230 views

System of “stochastic equations”

Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a ...
1
vote
0answers
287 views

Identifying sub graph in connected digraph [closed]

Hello I need some idea for a quick algorithm. Given a strongly connected undirected graph G with weighted edges, I would like to identify induced sub graph(it is required to be weakly connected) of ...
24
votes
2answers
1k views

What is the best exact algorithm to compute the core of a graph?

A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H. http://en.wikipedia.org/wiki/Core_%...
15
votes
1answer
426 views

Graph decompositions for combining “local” functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...