Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.
2
votes
1answer
15 views
Term for size of maximum independent set
An independent set is a set of vertices in a graph, no two of which are adjacent.
A maximum independent set is a largest independent set for a given graph G.
Is there a standard term for the size of ...
1
vote
1answer
54 views
Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge
Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.
Explanation of the terms:
$k$-regular means that all ...
3
votes
0answers
41 views
DAG Minimum Path Cover in O(nlogn)?
I asked this question on stackoverflow, but was suggested to post to same here. So here goes.
The following problem was asked in the recent October 20-20 Hack on Hackerrank :
Evil Nation A is ...
0
votes
0answers
24 views
Traveling Salesman with Held and Karp Algorithm
I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP.
I have implemented it with bitmask, and it's something like this:
...
5
votes
3answers
45 views
Negative weight cycle vs maximum weight cycle
I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph.
If we negate the weight of each edge, ...
3
votes
1answer
29 views
Unranking paths in a graph/lattice
A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified ...
1
vote
1answer
33 views
A technical clarification on subgraph isomorhism
Let $G$ be a graph on $|\mathcal{V}(G)|$ vertices. If $H$ is another graph that contains a clique of size $|\mathcal{V}(G)|$, then does it mean $G$ is subgraph isomorphic to $H$? Does this mean that ...
6
votes
2answers
71 views
Software for testing graph homomorphism
I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to ...
-4
votes
0answers
59 views
0
votes
0answers
24 views
2
votes
2answers
81 views
Direct reduction from Near-Clique to Clique
An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ ...
3
votes
1answer
36 views
Courcelle's Theorem: Looking for papers
I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.
I am only a beginner ...
0
votes
0answers
18 views
Saturating all augmenting paths with the minimum edge capacity in max flow
To find the maximum flow in a graph, why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back-edges? I mean, what is the ...
1
vote
1answer
31 views
Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?
In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first ...
5
votes
2answers
135 views
Points-in-a-plane from HackerRank
I've been struggling with this problem for days now, making no progress:
There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your ...
7
votes
1answer
31 views
Is the per-vertex error over a PageRank iteration monotonically decreasing?
It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.
However, is the same ...
1
vote
0answers
46 views
Recalculate max-flow after removing edge with 1 capacity [closed]
So I have some graph, and I know what it's max flow is based of the Ford-Fulkerson Algorithm.
With this information, I need to know how to find a new max flow when I remove an edge of this graph with ...
2
votes
1answer
73 views
A* to find the longest path in a directed cyclic graph
I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph.
My attempt was to write it so that ...
1
vote
2answers
130 views
Shortest path that passes through specific node(s)
I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
3
votes
0answers
36 views
Graphs invariant to permutations of vertices
I am reading a paper on Semi Supervised Learning and I am confused about a term. The paper talks about graphs that are invariant to permutations of the vertices. Can somebody explain or perhaps give ...
2
votes
1answer
49 views
How to reduce the number of crossing edges in a diagram?
I am working on a diagram editor.
Diagrams display 2D shapes (nodes) connected with connectors (edges).
I'd like to add an operation that, given a selection of nodes, "disentangles" them: it ...
3
votes
1answer
104 views
Running Floyd-Warshall algorithm on graph with negative cost cycle
I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ...
2
votes
1answer
43 views
Is there a graph product that is multiplicative in independence number?
I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help ...
2
votes
1answer
51 views
What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?
Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
2
votes
1answer
30 views
a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph
Suppose I have a set of small subgraphs $A=\{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i| \ll |G|$, which together span the original graph
$$
G= \bigcup_i G_i
$$
My question is ...
0
votes
1answer
42 views
Clarification sought for definition of a cut that respects a set A of edges in Graph Theory
From CLRS (3rd edition), I came have this question on page 626:
Given these definitions from the text,
DEFINITIONS:
Given an undirected graph G = (V,E),
1. A CUT (S ,V-S) of G is a partition of V,
...
1
vote
0answers
48 views
Counting modified perfect matchings
Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, ...
-2
votes
1answer
32 views
Show that every graph without self loops and with two or more nodes contains two nodes that have equal degrees [closed]
An undirected graph is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges. The number of edges at a particular node is ...
0
votes
0answers
27 views
Prove that an undirected graph with at least (n^2 - 3n + 4) / 2 edges is connected [duplicate]
I am trying to to prove that every undirected graph, with $n$ nodes and at least $(n^2 - 3n + 4) / 2$ edges, is connected.
Now I came up with this, possibly unorthodox solution and wondering if it is ...
2
votes
1answer
50 views
Approximation algorithm for Feedback Arc Set
Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set.
I want to find out about is ...
1
vote
2answers
87 views
Find a simple path visiting all marked vertices
Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of ...
4
votes
1answer
36 views
What is the optimal solution to prove the reachbility of a node from the root?
I have a finite automaton with these properties:
Contains cycles
It's a directed graph
All the states/nodes are initialy reachable from the initial state
It has final states but I guess it isn't ...
2
votes
0answers
30 views
Finding embedded DAG in another DAG based on colors
I am looking for some graph theory concepts and definitions around embedding a DAG into another DAG. I could only find a few lines on Wikipedia around this so I wonder if someone can help me find ...
4
votes
1answer
73 views
Simple graph canonization algorithm
I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
2
votes
2answers
178 views
Shortest Minimax Path via Floyd-Warshall
I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.)
...
3
votes
3answers
237 views
What is the significance of negative weight edges in a graph?
I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.
...
0
votes
1answer
42 views
Where are back edges in a DFS tree?
As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are ...
4
votes
2answers
67 views
Number of 5-cycles and 6-cycles in a simple graph
Is there any formula for computing the number of 5-cycles and 6-cycles in a simple undirected graph?
3
votes
2answers
51 views
Complete graph invariant
Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
0
votes
1answer
72 views
Algorithm for Graph merge and recompute
I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I ...
1
vote
0answers
38 views
Is there a word/name for the node(s) in a graph with the minimal cumulative path length to a set of other nodes?
In other words, given a graph with nodes $N=\{n_0,n_1,...,n_j\}$, and a set of nodes in the graph $M=\{n_a,n_b,...,n_k\}$ with $M\subseteq N$, I'm looking for what to call the node or nodes $n'$ which ...
5
votes
1answer
74 views
Complexity of finding a spanning tree that minimizes the maximum interference
Given $n$ nodes in the plane, connect the nodes by a spanning tree.
For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
5
votes
1answer
127 views
Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.
I tried to look it up at a few places (including ...
3
votes
1answer
39 views
Max cut in cubic graphs
The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states
A maximal cut of a cubic graph can be computed in polynomial time
Browsing ...
2
votes
2answers
188 views
Detecting cycles in undirected graph
I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, ...
5
votes
1answer
135 views
Dividing a weighted planar graph into $k$ subgraphs with balanced weight
I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
3
votes
0answers
55 views
Drawing Zonotopes from an Adjacency Matrix
I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange.
Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all ...
1
vote
0answers
37 views
Matching k-partite graphs where all sets may only share edges with one of the sets
I'm not terribly well-versed in CS (I only just a few moments ago learned what a k-partite graph is), so forgive me if this is an obvious question.
I'm wondering how to determine if a given graph ...
4
votes
1answer
170 views
Data structure for storing edges of a graph
I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering ...
2
votes
1answer
144 views
Finding path with minimum weight
There is a river which can be considered as an infinitely long straight line with width W.
There are A piles on the river, and B types of wooden disks are available.
The location of the $i$-th pile ...
