0
votes
0answers
4 views

Graph partition with an objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
1
vote
2answers
29 views

Concrete and simple applications for bipartite graphs [on hold]

I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.
0
votes
1answer
34 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
0
votes
0answers
19 views

Is the vertex cover problem NP-Hard in general graphs and in P for bipartite graphs? [closed]

Wikipedia says that finding the minimum vertex cover is NP-Hard. However, for bipartite graphs, I can solve the maximum matching problem with Hopcroft-Karp in polytime and then, through Koenigs ...
2
votes
2answers
97 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
-1
votes
2answers
50 views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, ...
2
votes
2answers
39 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
0
votes
1answer
81 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
0answers
84 views

Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
3
votes
3answers
98 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
0
votes
1answer
28 views

Minimizing the following objective function with matrices

I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree ...
2
votes
1answer
24 views

Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want ...
2
votes
1answer
98 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
1
vote
1answer
24 views

How many times an empty 4-cycle can be counted in an undirected graph?

I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle ...
1
vote
1answer
39 views

Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
2
votes
1answer
91 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
1
vote
2answers
53 views

Simple path in a graph, within a given range of lengths [closed]

Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$. So, for example, $N=4, ...
2
votes
4answers
124 views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
2
votes
1answer
63 views

Using interval graphs to find authorship disputes

The first chapter of the book "Graphs and their uses" by Oystein Ore says that interval graphs can be used to resolve authorship disputes, but I couldn't find any details. How does this work? What ...
1
vote
1answer
81 views

Pancake Graph with order 4 [closed]

Pancake graph have least diameter & degree (log n/ log log n) pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}. pancake Graph with ...
0
votes
0answers
71 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
1
vote
1answer
84 views

Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that : 1.every simple cycle in ...
0
votes
1answer
72 views

Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST: Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$. I want to find another minimum ...
2
votes
1answer
114 views

clique, independent set, and minimum vertex cover

I was given a graph problem with 3 different questions and 1 set of answers. The problem is described below. The problem that I'm having is that it seems to me that the answer to all the questions is ...
0
votes
1answer
55 views

On the minimum order of a maximal independent set in cycle graphs and path graphs

I can see from this question that a $K_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least $$\frac{n}{2e/n + 1} \tag{1} $$ Since for a $C_{n}$/$P_{n}$ we ...
1
vote
1answer
132 views

Widest path algorithm steps [closed]

I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate ...
-2
votes
1answer
134 views

Modifying Dijkstra’s algorithm to favor the path with least amount of edges

I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths. I am thinking to add another data ...
2
votes
3answers
849 views

Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This ...
1
vote
2answers
57 views

Showing that graph of spanning trees are connected

Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$. We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in ...
1
vote
0answers
134 views

Maximum subset intersection problem

Given N finite subsets of the finite universe set E, it is necessary to find the intersection which contains maxumum number of subsets. Let call this problem MSI (Maximum Subset Intersetion). Firstly ...
3
votes
0answers
81 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
3
votes
2answers
2k views

Is it possible to modify dijkstra algorithm in order to get the longest path? [duplicate]

Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?. My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the ...
4
votes
2answers
117 views

Bipartite Graph Game

So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
2
votes
1answer
102 views

topological sort equivalence

For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering. Question: can all ...
3
votes
0answers
50 views

Help for implementing the maintenance of the connected components in the Euclidean plane in logarithmic time

I am aware of a logarithmic-time algorithm to maintain the connected components of graphs in the Euclidean plane (D. Eppstein, GF Italiano, R. Tamassia, RE Tarjan, J. Westbrook, and M. Yung. ...
4
votes
1answer
74 views

How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?

I have found an interesting exercise in my introduction to graphs workbook: Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}$. ...
1
vote
1answer
243 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 ...
0
votes
0answers
52 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 ...
2
votes
1answer
1k 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
776 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
43 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
44 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
170 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 ...
4
votes
1answer
49 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 ...
5
votes
1answer
36 views

Subgraph isomorphisms: does large out-expansion imply large in-expansion?

Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of ...
1
vote
1answer
321 views

Sabatier conjectures

While I was doing CLRS (3rd edition), I came across this question on page 629: Professor Sabatier conjectures the following converse of Theorem 23.1: Let $G = (V,E)$ be a connected, undirected ...
1
vote
1answer
134 views

r-regular graph and hamiltonian path

I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me. Question: Let $G = (V,E)$ be an undirected $r$-regular graph ...
1
vote
1answer
100 views

How to perform alphabetically ordered DFS?

I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. ...
1
vote
1answer
50 views

Find the number of topological sorts in a tree

Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself. I've tried thinking what would be the best for m to define it but couldn't get ...
2
votes
2answers
167 views

Max-Flow: Detect if a given edge is found in some Min-Cut

Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$. Another question is, how do ...