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

1
vote
2answers
62 views

Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
6
votes
5answers
590 views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
-1
votes
1answer
14 views

Checking a property of all of the cycles in a graph

Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then ...
3
votes
1answer
136 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
0
votes
0answers
18 views

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ? I've seen it stated that one can apply a maximum flow ...
1
vote
1answer
36 views

Is a subgraph either a spanning subgraph or a full subgraph?

A graph $G' = (N' ,A')$ is a spanning subgraph of a graph $G = (N, A)$ iff $N ' = N$ and $A' \subseteq A$. A graph $G' = (N',A')$ is a full subgraph of a graph $G = (N, A)$ iff $N' ...
2
votes
1answer
17 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
1
vote
1answer
65 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [on hold]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
38
votes
6answers
21k views

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
3
votes
1answer
45 views

Is the minimal number of colors needed to color a graph some fixed number?

Consider to following decision problem: Input: Undirected graph $G=(V,E)$ Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices ...
1
vote
1answer
20 views

Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

Given a directed weighted graph, is there an algorithm that does the following: Removes as many edges possible. Reduces as many weights as possible. Given the constraint that the net weight of all ...
1
vote
0answers
25 views

TSP heuristics for limited distance information [closed]

this is my first question on ComputerScience beta. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for ...
3
votes
0answers
12 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 ...
4
votes
2answers
78 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
0
votes
1answer
29 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear. Given the following ...
0
votes
0answers
15 views

A way to order a shortest path tree

Given the shortest path tree of a directed graph G=(V,E) and w: E-> R , source vertex s and an assumption that there are no negative cycles in the graph. In the homework assignment we need to find ...
0
votes
1answer
88 views

Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
1
vote
1answer
60 views

Lower bounding the minimum equivalent graph

The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$. The minimum equivalent graph $G' = ...
3
votes
1answer
28 views

Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...
-2
votes
0answers
12 views

minimum spanning tree vs unique light edge [on hold]

A Graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. My question is why the converse is not true.
0
votes
0answers
24 views

Finding the second lightest path in a graph

Assume I have a weighted, directional graph with no cycles. What is the most efficient way to find the second lightest path from the source vertex to a given vertex?
1
vote
0answers
16 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 ...
2
votes
0answers
308 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 ...
1
vote
1answer
21 views

Proving a language to be Recursively Enumerable?

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L ...
-1
votes
1answer
23 views

Is the empty set a dominating set? [closed]

Is the empty set a dominating set? I don't think it is, because in an empty set there are no vertices to dominate. Is my reasoning correct?
0
votes
1answer
36 views

Can I find a clique with more than 2 nodes in a bipartite graph?

As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?
1
vote
1answer
16 views

Is there any relation between Global minimum cut problem and Maximal independent set?

I have simple undirected graph. I want to determine a size of minimum vertex cover, a size of maximal independent set and a size ...
1
vote
1answer
79 views

Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem: I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on ...
6
votes
1answer
254 views

Generate scale-free networks with power-law degree distributions using Barabasi-Albert

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
2
votes
2answers
74 views

Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
5
votes
3answers
3k views

How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring: ...
4
votes
0answers
35 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 ...
1
vote
1answer
19 views

Path in digraph passing through given set of vertices

Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f ...
0
votes
0answers
42 views

What are the application of $\beta$-frugal coloring of Graph and Hypergraph?

A proper coloring of a graph $G$ is called $\beta$-frugal if no color appears more than $\beta$ times in the neighborhood of any vertex of $G$. I am well aware about the application of graph color ...
3
votes
1answer
34 views

Finding all paths between a set of vertices in a DAG

Given a graph G= (V, E) that is: directed, acyclic, non-weighted, may have more than one edge between two vertices (thus, source and destination are not enough ...
0
votes
1answer
36 views

What does every root is at the same level mean

My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level. My conceptual understanding: All this time, I was led by my textbook to believe a root is ...
6
votes
1answer
455 views

Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
0
votes
1answer
38 views

Application of shortest vertex-disjoint path with time window

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to ...
0
votes
1answer
34 views

Algorithm to recognize Strongly Regular Graph (SRG)

I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.
3
votes
3answers
823 views

Application of Four color theorem

I was reading up on Four color theorem and am wondering if there is any practical application of it .( I dont think seperating the map into four different colors can be considered an application) I ...
1
vote
0answers
71 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
-1
votes
1answer
31 views

Max-Flow Min-Cut Theorem Intuition

What is the intuition behind the Max-Flow Min-Cut Theorem? I know that the Min-Cut is the dual of Max-Flow when formulated as a linear program, but the result seems artificial to me.
6
votes
2answers
120 views

Maximize distance between k nodes in a graph

I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance. In other words they ...
3
votes
0answers
61 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 ...
-2
votes
1answer
48 views

How many ways are there to add a node to a digraph?

In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices? Input digraph with $n$ vertices have following degree criteria : There ...
1
vote
0answers
29 views

How can we reduce a vertex cover problem to shortest acyclic orienatation?

I want to show that shortest acyclic orientation(SAO) is NP complete.Since vertex cover in Np complete so if vertex cover is reduced to shortest acyclic orientation then it will also be NP complete. ...
2
votes
1answer
48 views

TSP polynomial Time [closed]

How can it be proved that TSP cannot be solved in polynomial time ( Please bear that I don't have a hardcore computer science background).
2
votes
1answer
87 views

“Minimum” maximum flow with extra capacities

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
1
vote
1answer
27 views

Solving cycle in undirected graph in log space?

Setting Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ My Solution we show $UCYLE \in L$ by constructing $\mathcal M$ that decides ...
2
votes
1answer
24 views

Partitioning planar graph cycles based on chords

Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that: No sublist contains two vertices with a chord between them The last element ...