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

0
votes
0answers
5 views

Solving $Isomorphism$ using $AUTOM$ in polynomial time

Let $Iso$ be the language of all $<G,H>$ such that $G$ and $H$ are isomorphic, and $AUTOM$ be the language of all $G$'s such that $G$ has a non-trivial automorphism. I'd like to show that, ...
0
votes
2answers
25 views

A* graph search heuristicfor pathfinding

A* needs a consistent heuristic to work on a graph. So I'm not sure if the heuristic of a straight line (bird flight) can be used. For example: the costs to travel to a neighbors node is always ...
0
votes
1answer
20 views

Reweight general weighted graph to distinct graph for using Borůvka's

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it? I can't seem to think of a way to make a ...
2
votes
1answer
52 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
1
vote
1answer
63 views

How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
2
votes
0answers
34 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 ...
3
votes
1answer
73 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} ...
2
votes
0answers
48 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 ...
4
votes
0answers
55 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, ...
0
votes
1answer
43 views

Finding undirected cycles in linear time (triangulating graphs while minimizing degree)

In the article ["Triangulating Planar Graphs While Minimizing the Maximum Degree"] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating ...
0
votes
3answers
77 views

Given a minimum vertex cover can we find all the others in polynomial time?

Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem ...
1
vote
0answers
53 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ...
0
votes
1answer
33 views

To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?

Given two lists of non directional graph edges e.g. [(1,3),(3,5),(5,1),(5,7)] [(4,5),(2,3),(3,4),(4,2)] In order to check if the two graphs are isomorphic is it enough to count the vertices with the ...
1
vote
1answer
47 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, ...
0
votes
0answers
18 views

Algorithm: “Minimum” maximum flow with extra capacities [duplicate]

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, ...
0
votes
0answers
24 views

Stable Marriage or Assignment Problem?

I have a question pertaining to committee selection. Let $C = c_{1}, c_{2}, \ldots, c_{n}$ be n Committees and $S = s_{1}, s_{2}, \ldots, s_{m}$ be m Students. Each $c_{i}$ in C ranks their ...
1
vote
1answer
56 views

Knight's tour from all starting positions

Is it true that for all $n\geq 5$, there is a knight's tour of an $n\times n$ chessboard beginning at every square? For example, is it correct, that there is no solution for a $5\times5$ board, with ...
3
votes
1answer
19 views

Do $s$-$t$ cuts partition contingent vertices?

The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements ...
0
votes
0answers
11 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 ...
9
votes
1answer
105 views

Determining the minimum number of edges to add in order to be 3-connected

A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a ...
1
vote
2answers
41 views

Can't see how this can be true: any connected undirected graph $G$ contains vertex v such that removing v results in another connected Graph $G'$ [closed]

I am attempting to prove this result but I found a case where I can easily disprove this statement. Suppose $G$ is a graph with two nodes u, v and an edge (u,v) and respective self edges, then ...
4
votes
1answer
49 views

Distribution of cycles length in a graph

Given a random directed Graph G: $$ G=(V,E) \\ \lvert V \rvert = n , \lvert E \rvert = k $$ where for each vertex, either: $$ d_{incoming}(v) = 1 , d_{outgoing}(v) = 1 $$ meaning - for each ...
0
votes
1answer
41 views

Tournament graph

I have to prove the following assertion: given a tournament graph with $n$ vertices, $n\geq 5$, there can be made an arrangement of the arcs such that between any two vertices exists at least one way ...
2
votes
0answers
29 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
2answers
41 views

Difference between edges in Depth First Trees

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after ...
-1
votes
1answer
27 views

Vertex degree in De Bruijn graphs

How can I find the degree of a vertex in a De Bruijn graph? Also, given a vertex, is there an easy way to find which other vertices it is connected to?
3
votes
1answer
54 views

Assign undirected edges in a mixed graph to make graph cyclic/acyclic

What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle. It ...
5
votes
3answers
281 views

Constructing a random Hamiltonian Cycle (Secret Santa)

I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints: No recipients within the immediate family Nobody should get who they got last year The ...
0
votes
0answers
14 views

Prove a characterisation of the minimum directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
3
votes
1answer
83 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
5
votes
1answer
71 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 ...
7
votes
2answers
282 views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, ...
1
vote
1answer
62 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
1answer
37 views

Single Source Shortest Path: What does the weights on the vertex and edges tell you?

In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path. ...
2
votes
1answer
68 views

Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

Let G = (V,E) be a unit-capacity graph with n vertices and m edges. Let T denote all the spanning trees in G. If we run Karger's algorithm, we will get a random spanning tree in T formed by the ...
1
vote
1answer
20 views

Construction of graph with given Wiener Index

Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be ...
0
votes
2answers
121 views

Show that the tree resulting from BFS is a spanning tree?

Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is ...
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 ...
0
votes
1answer
53 views

Calculating genus of graph

How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.
1
vote
0answers
25 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) ...
2
votes
2answers
56 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
2
votes
1answer
61 views

Disconnecting a complete graph by removing edges randomly

Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph. I want to find out the minimum number of edges that I must remove ...
0
votes
0answers
32 views

Cycles in graphs with optional edges, redux: labelled optional edges

In a previous question, I asked how much information is needed to encode the possible cycles in a directed graph with $N$ "optional" edges given only the subset of the optional edges that are present ...
0
votes
0answers
17 views

Assign colors to vertices of a 3 colorable graph [duplicate]

Black Box tell is g(v,e) is 3 colorable or not. How can we use this graph to assign the colors to a 3 colorable graph?
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)$ ...
0
votes
1answer
29 views

How do deal with the following situations using Prim's algorithm?

Consider the following Graph We want to generate the MST using Prim's algorithm. Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other ...
2
votes
1answer
47 views

Characterizing cycles in a directed graph with optional edges

Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of ...
0
votes
0answers
32 views

What is an example of a minimum weight connected subset T of edges from a weighted connected graph G?

What is an example of a minimum weight connected subset T of edges from a weighted connected graph G? Can I just take two edges that are connected and have min combined weight and call that the min ...
2
votes
2answers
83 views

Is there a difference between perfect, full and complete tree?

Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?
0
votes
0answers
27 views

Merging two disconnected graphs

Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's. I have two ...