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
18 views

Understanding terms related to 2 SAT algorithm

Recently I am learning about solution of 2-Satiability problem using SCC(Strongly Connected Component). There is a theorem related to this problem given below: Theorem 2: The formula F is true if and ...
-1
votes
1answer
39 views

Comparing two graphs, finding vertices that changed their positions [on hold]

I have a task of comparing two organisation charts. These chart objects are described as a set of nodes (people) where each has a unique ID field and a parent ID field (pointing to another node's ...
5
votes
1answer
34 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
-3
votes
0answers
35 views

Diameter and some Formula on Graph Theory

in an undirected graph G, we define: Diameter is maximum of minimum paths between two vertex of a graph. L(s) is maximum length of minimum paths from s to ...
2
votes
0answers
39 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 ...
0
votes
0answers
12 views

Simple C/C++ library for network graph manipulation [migrated]

I'm currently working on a research project that makes use of proprietary software. I'm trying to replace the proprietary C libraries for graph representation. Doing this will make it easier to ...
0
votes
1answer
37 views

Christofides algorithm: why must an MST have even number of odd-degree vertices?

This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it. I assume that a minimum spanning tree must have an even number of odd-degree ...
1
vote
0answers
24 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' = ...
0
votes
0answers
22 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
0answers
62 views

Totally unimodular <=> polynomial time?

Crossposting due to recommendation. I formulated a MIP problem which I didn't expect to be unimodular. The problem is to find a minimum complete sequence in a strongly connected digraph. That is, ...
3
votes
1answer
68 views

Is a “tree” with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

For the following $2$ cases: (1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all) (2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$) Are they considered a valid tree? It seems ...
4
votes
1answer
109 views

Finding all circuits that contain a given edge

Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that ...
3
votes
1answer
41 views

Sufficient condition for simple graph isomorphism?

Say I have two simple graphs, $A$ and $B$ In $A$, I know: one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc. one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc. etc. ...
0
votes
1answer
59 views

Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?

I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max ...
1
vote
0answers
16 views

Understanding the correctness of the Euler Tour Technique

I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia: Given an undirected tree presented as a set of edges, the Euler tour ...
1
vote
0answers
17 views

Stable matching of producers, consumers and objects

Has the following version of the stable matching problem been studied? There are $k$ types of objects. There are $n$ producers, each of whom can produce a single object of any type, and has a ...
0
votes
1answer
37 views

undirected graph without weights and DFS [closed]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
0
votes
2answers
91 views

Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ [closed]

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a ...
5
votes
1answer
94 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
1answer
30 views

Examples for directed graphs with super polynomial cover time

The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes. For undirected graphs the cover time is upperbounded by $O(n^3)$. What about ...
3
votes
1answer
117 views

Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid

An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that: the endpoints of ...
0
votes
1answer
36 views

Not Hamiltonian is in NP Class? [duplicate]

I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest. From this book and other study in complexity theory, I have seen the following ...
4
votes
0answers
29 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 ...
2
votes
1answer
76 views

Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
2
votes
1answer
33 views

What is an edge hop?

I've tried googling it, but found nothing. Here is the context it's in: From Bayesian Reasoning and Machine Learning: Adjacency matrices may seem wasteful since many of the entries are zero. ...
2
votes
0answers
22 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 ...
4
votes
1answer
79 views

Term for a matching which is perfect on one side only

What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, ...
0
votes
0answers
12 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
32 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
25 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
55 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
3answers
96 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
52 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
96 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
61 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
60 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
69 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
85 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
54 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
35 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
70 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
43 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
63 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
23 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
16 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
115 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
45 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
51 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
44 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 ...