Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

14
votes
0answers
133 views

Finding an st-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path $P$ which minimizes ...
14
votes
0answers
260 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
7
votes
0answers
130 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G ...
6
votes
0answers
219 views

Graph isomorphism problem for graphs with colored directed edges

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
6
votes
0answers
129 views

Counting Graphs (Minimum Number of Bits Required To Encode Certain Graphs)

Background: I am interested in finding succinct data structures for certain types of graph classes, particularly partial k-trees. For general graphs, there are $\binom{\binom{n}{2}}{m}$ graphs on $n$ ...
6
votes
0answers
95 views

What is the proof for the lemma “For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge”?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
5
votes
0answers
54 views

Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
5
votes
0answers
123 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
5
votes
0answers
66 views

Decomposition of graphs that uses centers

Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason ...
5
votes
0answers
225 views

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a ...
5
votes
0answers
643 views

A variation in Ford-Fulkerson algorithm

Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow. I was thinking that when we augment a ...
5
votes
0answers
249 views

Worst-case sparse graphs for Hopcroft-Karp Algorithm

Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
5
votes
0answers
314 views

Kosaraju-Sharir algorithm and the inserted vertex

This is a question from my homework and I need some help. We are trying to run Kosaraju-Sharir algorithm over $G$, adirectional graph with arcs $(u,v)$. In the first DFS pass we inserted vertex $u$ ...
4
votes
0answers
42 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
4
votes
0answers
68 views

Recognize if graph has Hamiltonian cycle from subgraphs

There is a graph G, which is not known to me. Instead I am given the multiset of all graphs that are obtained by deleting a single vertex from G. My task is to figure out, from all of these subgraphs, ...
4
votes
0answers
101 views

Necessary and sufficient condition for unique minimum spanning tree

This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13] . Prove that an edge-weighted graph $G$ has a unique minimum ...
4
votes
0answers
83 views

What is this prize-collecting optimization problem with travel times?

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. ...
4
votes
0answers
51 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
4
votes
0answers
83 views

Partition a bipartite graph to a complete matching and an independent set

I am looking for a reference for the following theorem: Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$). There is a nonempty subset $Y_1 ...
4
votes
0answers
303 views

Shortest path in graph - upgrade an algorithm

We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our ...
4
votes
0answers
113 views

Beating fair colorings with few edges

I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can ...
3
votes
0answers
32 views

Directed acyclic graphs and Latin Squares

Every Latin square corresponds to a directed acyclic graph with a lattice arrangement, and whose edges indicate label order (<). For example: I'm interested ...
3
votes
0answers
33 views

Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
3
votes
0answers
17 views

Efficient algorithms for mutual, inverse, or round-trip Personalized PageRank

I'd like to implement a similarity between two nodes (X and Y) of a graph based on a simple extension of the Personalized PageRank algorithm, either: (Mutual PageRank): the product of the PPR of Y ...
3
votes
0answers
73 views

Genetic algorithm crossover technique for solving graph colouring problem

I am trying to develop a genetic algorithm to solve a graph colouring problem. The problem is the standard graph colouring problem, given a graph $G = (V,E)$ where $V$ is the set of vertices $V=\{0 ...
3
votes
0answers
200 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
3
votes
0answers
89 views

Steiner tree wiring problem

I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner ...
3
votes
0answers
105 views

Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof ...
3
votes
0answers
53 views

Help for implementing the maintenance of the connected components in the Euclidean plane in logarithmic time

I am aware of a logarithmic-time algorithm to maintain the connected components of graphs in the Euclidean plane (D. Eppstein, GF Italiano, R. Tamassia, RE Tarjan, J. Westbrook, and M. Yung. ...
3
votes
0answers
48 views

Graphs invariant to permutations of vertices

I am reading a paper on Semi Supervised Learning and I am confused about a term. The paper talks about graphs that are invariant to permutations of the vertices. Can somebody explain or perhaps give ...
3
votes
0answers
110 views

Drawing Zonotopes from an Adjacency Matrix

I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange. Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all ...
3
votes
0answers
896 views

Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
2
votes
0answers
53 views

Pagerank is equivalent to degree centrality

Can someone explain why pagerank defined for undirected graph with no damping factor is equivalent to the degree? $\sum_{j\in N(i)}{\frac{p(j)}{d(j)}} = d(i)$ I looked up every book I could, but ...
2
votes
0answers
36 views

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
2
votes
0answers
143 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
2
votes
0answers
83 views

What is a best known algorithm for finding diameter of undirected graph?

What is best known algorithm (approximate or exact) for finding diameter of a large undirected graph? The diameter is defined as longest of shortest paths between any two nodes. I know that naive ...
2
votes
0answers
239 views

Showing that the language of graphs and nodes on an odd cycle is in NL

Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear ...
2
votes
0answers
31 views

In case of a given graph , Is that possible to build trapezoidal map in linear time

[This regarding to Computational geometry in CS] Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G). I'd like to build a trapezodial map out ...
2
votes
0answers
119 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
2
votes
0answers
328 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
2
votes
0answers
40 views

Finding embedded DAG in another DAG based on colors

I am looking for some graph theory concepts and definitions around embedding a DAG into another DAG. I could only find a few lines on Wikipedia around this so I wonder if someone can help me find ...
2
votes
0answers
502 views

Effect of increasing the capacity of an edge in a flow network with known max flow

I need your help with an exercise on Ford-Fulkerson. Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance. Now suppose you are ...
2
votes
0answers
88 views

Complexity of finding a subset of vertices within distance k of each other, given a set of vertices

I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
2
votes
0answers
78 views

End-Of-The-Line Augmented Problem of PPAD

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line: End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed ...
2
votes
0answers
60 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ ...
2
votes
0answers
127 views

Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each ...
2
votes
0answers
91 views

Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
2
votes
0answers
92 views

Graph conductance - program/code/library

Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing? Think it is quite well-known problem, ...
2
votes
0answers
72 views

IDS algorithm optimality for grid?

My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement. I read that the IDS algorithm is optimal, but in my case is not optimal ...
1
vote
0answers
18 views

Coloring a 3-Colorable graph with O(logn) colors

Assume we have a polynomial algorithm that can get approximation ratio of $\frac{1}{2}$ to the Independent-Set problem. I need to prove that there exists a polynomial algorithm that for a 3-Colorable ...