0
votes
0answers
4 views

A bound for the minimum vertex cover of special graphs

For a complete graph, the size of minimum vertex cover is $\lceil n/2 \rceil$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex ...
1
vote
0answers
27 views

Upper Bounds on Characteristic Path Length of Graphs

Characteristic (average) path length is defined here: http://cs.stackexchange.com/a/7538/20256 I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive ...
3
votes
2answers
94 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
1
vote
1answer
55 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
5
votes
2answers
152 views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
3
votes
1answer
70 views

Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts. Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in ...
7
votes
1answer
133 views

Research in Graph Theory versus Graph Algorithms

I have a very generic question to ask. It is related to research. I'm interested in Graph theory. I have done a course in it. I have done some topics related to both graph theory as a point of ...
0
votes
2answers
41 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
2
votes
1answer
43 views

Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph. The algorithm I have come up ...
2
votes
1answer
42 views

Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$. Is answering to that problem yes or no equivalent to subset-sum problem? What would ...
5
votes
1answer
110 views

Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$). Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs? Perhaps some motivation is in place: the ...
1
vote
2answers
59 views

Concrete and simple applications for bipartite graphs [closed]

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
41 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 ...
2
votes
2answers
127 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
77 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
47 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
120 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
98 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
170 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 ...
-1
votes
1answer
45 views

Minimizing the following objective function with matrices [closed]

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
40 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
108 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
27 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
44 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
98 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
74 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, ...
3
votes
4answers
195 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
69 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
102 views

What is the order of the Pancake graph in Given example & what are the properties of Pancake graph? [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
110 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
163 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
78 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
142 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
65 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
241 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
218 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
1k 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
62 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
157 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
87 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
132 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
113 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
77 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
308 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
56 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
2k 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
1k 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
44 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 ...