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
1answer
12 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
32 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 ...
2
votes
1answer
30 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
31 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 ...
1
vote
1answer
34 views

Split graph into 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 ...
0
votes
1answer
34 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
30 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.
1
vote
0answers
49 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
28 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.
1
vote
1answer
21 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
0answers
23 views

Precoloring extension on graphs for which coloring is hard

I am reading Niedermeier's book Invitation to Fixed-Parameter Algorithms. In Chapter 15, the author introduces the precoloring extension problem: given a graph with some vertices having preassigned ...
6
votes
2answers
114 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
46 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
45 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 ...
0
votes
0answers
23 views

A graph not embeddable in closed surface [closed]

Let $G$ be an $n$ vertex graph with edges of $G$ greater than $\Delta(n^2)$. Suppose that $G$ contains a complete bipartite graph $K_{t,t}$ as a minor. How can we use this information to prove that ...
1
vote
0answers
28 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
45 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).
1
vote
1answer
21 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 ...
-1
votes
0answers
29 views

$G$ has an Euler tour iff in-degree($v$)=out-degree($v$)

A simple cycle is a path in a graph that starts and ends at the same vertex without passing through the same vertex more than once. A complex cycle, is a cycle that passes through the same vertex ...
2
votes
1answer
23 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 ...
1
vote
0answers
31 views

Terminology for a graph with ports on its nodes

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
4
votes
1answer
109 views

Gray Code Generation

I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the ...
4
votes
1answer
99 views

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
2
votes
1answer
59 views

Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
2
votes
1answer
31 views

Route planning for a car driver picking up people using public transport

We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation: Person 1 is driving with his car from the south of city A to city B far in the north. ...
2
votes
1answer
76 views

Lowest Common Ancestor from children up?

I've seen algorithms for finding the lowest common ancestor from the root of a tree. However, I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom ...
0
votes
1answer
60 views

Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
0
votes
0answers
20 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector normalizing the ...
1
vote
0answers
22 views

Betweenness centrality and least average shortest path

TL;DR: How do I justify mathematically that vertices with the highest betweenness centrality do not necessarily have the smallest mean shortest path? I am currently studying the London Underground as ...
1
vote
1answer
46 views

Matching a set of paths to an incrementally generated graph

I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be ...
2
votes
1answer
69 views

Relationship between Independent Set and Vertex Cover

Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover. Does this imply that the complement of ...
-1
votes
1answer
49 views

Comparing two graphs, finding vertices that changed their positions

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
44 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.) ...
2
votes
0answers
47 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
1answer
46 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
55 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
75 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
65 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
70 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
112 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
48 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
61 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
21 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
20 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
39 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
95 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 ...
6
votes
1answer
176 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
37 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
126 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
37 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 ...