Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
1,041
questions
8
votes
0
answers
225
views
Complexity and approximability of maximum edge biclique problem on co-comparability graphs
A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph. Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete ...
9
votes
3
answers
6k
views
Finding number of cycles of length $k$ in a graph
We have $f(k) n^3$ time algorithm to determine whether a graph $G$ has a cycle of length exactly $k$.
How can we find how many such $k$-cycles are present in $G$ using the same or any other algorithm.
- 2,044
-2
votes
1
answer
1k
views
What's wrong with my linear programming formulation of longest path? [closed]
I have a directed graph which has cycles. Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$. Simple means the path has no ...
- 29
2
votes
1
answer
3k
views
Shortest simple path with minimum edge cost minus node reward
I have a directed graph which has cycles.
Each edge has a nonnegative weight and each vertex has a nonnegative reward.
Given two vertices s and t, I need to find a simple path (a path with no ...
- 29
1
vote
2
answers
9k
views
Algorithm for Max Network Flow with lower bounds and its complexity
I have built a max network flow graph that carries certain amount of people from a source to a destination. Now, I'd like to attach a lower bound $l_(e_)$ constraint to each edge $e$. But I don't know ...
- 55
3
votes
1
answer
960
views
network flow using minimum number of nodes
In a standard Ford-Fulkerson setting (directed graph $G$ with a source $s$ and a sink $t$), consider the problem of achieving a given amount of flow using the minimum number of nodes in the graph.
...
- 171
3
votes
1
answer
1k
views
Approximate Maximum Weight Matching
I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?
In my problem, I have a bipartite graph with N abound 1000 (#vertices on each ...
- 169
6
votes
1
answer
345
views
Linear ordering from weighted directed graph (kittens)
I want to build a website to find the cutest kitten(TM) there is. People can upload photos of their kittens, but also can vote on which kitten is the cutest. However, I don't want them to rate on a 1 ...
- 61
13
votes
2
answers
278
views
Complexity of computing a densest minor
Consider the following problem.
Input: An undirected graph $G=(V,E)$.
Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|...
- 1,096
-1
votes
1
answer
169
views
Representation suitable for reconstruction of a tree with bounded degree
I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
- 1,281
1
vote
1
answer
231
views
How to find the set of edges for the directed graph associated with a partial order?
I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$, where $f(a,b) = true$ if ...
- 113
27
votes
0
answers
1k
views
Counting Isomorphism Types of Graphs
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
- 6,033
0
votes
0
answers
71
views
Sparse matrix front reducing
There is a symmetric sparse matrix with large front. This matrix is created from graph. Element with position $(i,j)$ is not zero if nodes $i$ and $j$ are connected.
What algorithms can be used for ...
- 101
9
votes
2
answers
2k
views
Number of cycles in a Graph
How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m>k)$.
For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that ...
- 2,044
2
votes
1
answer
883
views
Simple Bisimulation algorithm
Is there a simple algorithm to calculate the maximal bisimulation relation of a graph/two graphs?
With simple i mean very easy implementation, complexity is not that important for us in this stage.
- 247
2
votes
0
answers
226
views
Quadratic Binary Optimization formulation of Steiner Tree problem
can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?...
4
votes
1
answer
190
views
H-induced Containment problem
In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fi xed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph ...
- 1,016
0
votes
0
answers
318
views
Subset of a vertex set with directed edge to all other vertices
I am posting the following question due to a lacking overview of relevant algorithms.
Given a directed graph $G=(V,E)$, how can you find a (minimal) subset $S$ of $V$ such that there for every vertex ...
10
votes
2
answers
527
views
Completeness spanning trees
A spanning tree of a graph is called a completeness tree if the set of
its leaves induces a complete subgraph in the host graph. Given a graph $G$
and an integer $k$, what is the complexity of ...
- 4,828
4
votes
1
answer
272
views
What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?
More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and ...
- 115
6
votes
1
answer
234
views
Efficient algorithm for a particular graph closure property
In the context of an unusual compiler problem, I have a graph in which the vertices are variables, and the edges correspond to whether the instruction set has an instruction that copies the source ...
- 173
16
votes
0
answers
2k
views
What is the fastest deterministic algorithm for incremental DAG reachability?
As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
- 519
0
votes
0
answers
202
views
Finding assignment-minimum complete k-partite graph cover
Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs?
I'm assuming this problem is NP-...
- 916
3
votes
1
answer
728
views
Termination of the Bellman-Ford algorithm in asynchronous distributed model
I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model.
The only requirement is $O(D)$ time complexity, where $D$ ...
- 141
1
vote
0
answers
537
views
Time complexity of clustering based on random walk
What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?
Can I use the complexity of eigen vector computation for this purpose?
The ...
- 11
4
votes
2
answers
2k
views
Online version of All pair shortest path when path weights are updated
Given
an undirected graph of $n$ nodes with weighted edges and
a sequence $S=((e,w),...)$ of updates, always decreasing, of the weight $w$ of edge $e$.
What is the online complexity of computing ...
- 101
2
votes
0
answers
95
views
Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?
Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so ...
- 21
-2
votes
1
answer
2k
views
Finding all paths with weight less than N from a source node
I have a directed graph that can have cycles and has weighted edges.
I'm having a tough time finding all the different paths you can take from a source node S with a distance less than X (sum of ...
- 7
13
votes
2
answers
933
views
What's the correlation between treewidth and instance hardness for random 3-SAT?
This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness.
For ...
- 11k
9
votes
1
answer
420
views
Finding optimal parallelization from general weighted undirected graph
I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:
Each node represents an image. Overlapping images are ...
- 191
11
votes
1
answer
253
views
maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph
Has this problem been studied before?
Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
- 769
5
votes
1
answer
1k
views
HITS and PageRank, topic drift problem
Reading some papers and articles about PageRank and HITS algorithm, I've figured out that there's a problem called topic drift problem. Googling it, (since I wanted to know more about it) I only found ...
- 133
1
vote
1
answer
728
views
Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances
If I need to find a shortest road (not great-circle) route between ~11,000 real world lat, long coordinates within a reasonable period of time. To further complicate things, there is no necessary ...
- 127
11
votes
1
answer
235
views
A survey on separators?
There are by now mountains of results on separators in graphs, from planar separator, tree separator, bounded tree width graphs, bounded genus graphs, etc, etc, etc. Is there any good updated survey ...
- 9,626
16
votes
2
answers
487
views
About generalized planar graphs and generalized outerplanar graphs
Any planar, respectively, outerplanar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.
Also, (outer-)planar graphs can be ...
- 332
6
votes
1
answer
14k
views
Flood fill vs depth first search
Is the flood fill algorithm the same as depth first search?
If not, how do they differ in complexity?
- 260
19
votes
5
answers
2k
views
Fast treewidth algorithms
I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
- 3,902
3
votes
1
answer
193
views
Efficient flow problem for a complex integer program
I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to ...
- 151
8
votes
1
answer
2k
views
Algorithms for finding clique in bounded-degree graph
Consider a graph with $n$ vertices and maximum degree $\Delta$. I would like to find if the graph has any $s$ cliques, where $s \leq \Delta$ and both of them are small compared to $n$. I only need to ...
- 3,498
6
votes
2
answers
193
views
Difference Sets
Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$
where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct.
We calculate the differences as: $$d=p_i-p_j\mod ...
- 179
12
votes
2
answers
831
views
Graph classes for which the diameter can be computed in linear time
Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
- 3,170
4
votes
0
answers
1k
views
Path finding algorithm to maximise points of interest along the route
I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point.
An user will enter the start location, the end location and the available time to travel. ...
2
votes
1
answer
812
views
Number of vertices at distance $k$ for each vertex of restricted sparse graph
My graphs has following restriction: undirected, connected, simple, unweighted,
and maximum degree of any vertex is 8. These are actually molecular graphs. Almost always maximum degree will be 4 but ...
- 1,281
5
votes
1
answer
1k
views
Partition graph into complete disjoint subgraphs while maximising sum of edge weights
Has this problem been studied?
We start with a complete, simple, undirected graph with edge weights. The problem is to delete edges so as to partition the graph into complete disjoint subgraphs while ...
- 51
4
votes
1
answer
241
views
Perfectly matchable edges in a bipartite graph
Consider the following problem:
Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume |...
- 263
7
votes
0
answers
981
views
Biconnected components of a directed graph?
I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
- 531
5
votes
4
answers
675
views
An algorithm for calculating the probability of a disease spreading through a graph
The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is (...
- 150
1
vote
1
answer
238
views
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
- 23
6
votes
1
answer
582
views
Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming
For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) ...
- 169
6
votes
0
answers
689
views
Weighted vertex-connectivity; global min vertex-cut
I am interested in the following problem:
Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex.
Output: a minimum weight subset of $V$ whose removal disconnects $G$.
When ...
- 1,166