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

12
votes
0answers
105 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 ...
12
votes
0answers
239 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
112 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
115 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
84 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
98 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$ ...
5
votes
0answers
62 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
186 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
539 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
243 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
108 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 ...
5
votes
0answers
299 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
40 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
75 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
104 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 ...
4
votes
0answers
291 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 ...
3
votes
0answers
46 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
3
votes
0answers
61 views

What is this discrete/combinatorial optimization problem?

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. ...
3
votes
0answers
150 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
71 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
52 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
139 views

DAG Minimum Path Cover in O(nlogn)?

I asked this question on stackoverflow, but was suggested to post to same here. So here goes. The following problem was asked in the recent October 20-20 Hack on Hackerrank : Evil Nation A is ...
3
votes
0answers
46 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
95 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
782 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
19 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 ...
2
votes
0answers
27 views

Common subgraph isomorphism with K vertex

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
2
votes
0answers
222 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
26 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
50 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 ...
2
votes
0answers
112 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
225 views

Potential values of minimum cost maximum flow 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
38 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
382 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
79 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
60 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
58 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
100 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
90 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
85 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
63 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
24 views

Efficient flood filling (seed filling)

I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) ...
1
vote
0answers
15 views

Can independence numbers of box products of cycles increase after stabilizing?

Is there an evidence or a proof that the independence of strong products of graphs can increase after stabilizing? I am interested in odd cycles only. Let $C_n$ be an odd cycle and $\alpha(G)$ ...
1
vote
0answers
63 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
1
vote
0answers
22 views

Why is it that in a butterfly network, there is a unique path from the input to the output?

Consider the a butterfly network as defined on the following OCW notes on page 208. An explantation of it can also be found on the following page. I was wondering if someone had a proof or an ...
1
vote
0answers
33 views

Upper Bounds on Characteristic Path Length of Graphs

Characteristic (average) path length is defined here: http://cs.stackexchange.com/a/7538/20256 I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive ...
1
vote
0answers
89 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
1
vote
0answers
41 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
1
vote
0answers
31 views

How to maximize the number of buyers in a shop?

There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
1
vote
0answers
240 views

Maximum subset intersection problem

Given N finite subsets of the finite universe set E, it is necessary to find the intersection which contains maxumum number of subsets. Let call this problem MSI (Maximum Subset Intersetion). Firstly ...