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

6
votes
1answer
497 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 ...
1
vote
3answers
100 views

Term for most degenerate tree with two children on every inner node

I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf. (Image from Penn State course STAT 557, Data Mining, lesson ...
4
votes
1answer
101 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
2
votes
0answers
58 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
3
votes
0answers
46 views

Heuristics to Find Circuits Allowing for Vertex Revists

I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem). See: ...
2
votes
0answers
21 views

Conjunctive Regular Path Queries and Subgraph Isomorphism

How do conjunctive regular path queries and subgraph isomorphism relate to each other? It seems that conjunctive regular path queries are a specialised form of subgraph isomorphism. The follow is ...
4
votes
1answer
126 views

Longest simple walk in a complete graph

A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice. A simple undirected ...
8
votes
1answer
63 views

About graphs whose edge set decomposes into perfect matchings

Is there a characterization of graphs whose edge set decomposes into a disjoint union of perfect matchings? One trivial class of such graphs are $d$-regular $(n,n)$-bipartite graphs. Their edge ...
3
votes
1answer
63 views

Simple algorithm for listing all 6-cycles in a directed graph

What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for ...
1
vote
0answers
33 views

Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix ...
1
vote
0answers
34 views

Sort graph nodes by density [closed]

Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which ...
4
votes
3answers
9k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
1
vote
0answers
28 views

Find all paths of length k [duplicate]

I have an adjacency matrix, call it A, representing a directed graph. I want to find all paths of length k. I know that A^k ...
7
votes
0answers
264 views

Graph isomorphism problem for labeled graphs

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 ...
1
vote
1answer
108 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 ...
0
votes
3answers
110 views

Do sparse graphs have to be large?

I'm looking for a good definition of sparse graphs. Is a sparse graph effectively a big one, with millions/billions of nodes? An example from real world is the Facebook graph. Or can sparse graphs be ...
1
vote
1answer
44 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 ...
2
votes
1answer
39 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
2
votes
1answer
33 views

Are there other interpretations of |G| than |V|, that is |V(G)|?

This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples ...
1
vote
1answer
45 views

What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
2
votes
0answers
30 views

Complexity of cubic graph decomposition

I am aware that deciding the existence of decomposition of a cubic graph into edge disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
0
votes
1answer
47 views

Finding common edges of two graphs [closed]

Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to ...
2
votes
2answers
683 views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ ...
0
votes
2answers
46 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
2
votes
1answer
44 views

Proving algorithm for removing nodes from a complete graph with two kinds of edges

Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a ...
1
vote
1answer
12 views

How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at ...
1
vote
2answers
34 views

Finding a minimum set of dependencies in a cycle-filled dependency graph

I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies. My goal is to find the smallest subset of ...
2
votes
1answer
74 views

Determine if items can be ordered grouping two simultaneous criteria

For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together. Obviously ...
2
votes
2answers
20 views

What are transitive successor and transitive predecessor in the graph?

I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are: transitive successor ...
3
votes
1answer
246 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 ...
4
votes
1answer
3k views

Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra algorithm is used only when ...
2
votes
1answer
45 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
3
votes
1answer
53 views

How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia) I know that the problem of counting the ...
1
vote
0answers
33 views

All paths of length n from a single graph vertex in a directed cyclic graph [duplicate]

Thanks in advance...looking for recommendations on an algorithm to find all paths of length n starting from a single node in a directed, cyclic graph. I am not concerned with at which node the path ...
2
votes
1answer
32 views

Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to ...
2
votes
1answer
50 views

Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees : 1) The first one: Node ...
0
votes
1answer
41 views

Graph theory, $n$ people sitting around table [closed]

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
3
votes
2answers
53 views

What is the appropriate algorithm for bipartite matching with constraints?

I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it). Let's say we have a lot of employees and a few jobs to be done. Each ...
4
votes
0answers
72 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
0
votes
2answers
130 views

scale-free networks and adjacency matrix

Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the ...
1
vote
1answer
59 views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
7
votes
2answers
185 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 ...
2
votes
1answer
104 views

Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do ...
0
votes
1answer
43 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 ...
3
votes
1answer
63 views

Travelling Salesman which can repeat cities

In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is ...
0
votes
1answer
15 views

Necessities for two undirected graphs being isomorphic

As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic: $|V| = |V'|$ $|E| = |E'|$ $G$ has $j$ nodes of degree $k$ ...
3
votes
1answer
126 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
3
votes
0answers
38 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
1answer
83 views

Locally finite graph without an optimal path

If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest ...
-2
votes
2answers
77 views

Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?