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

11
votes
0answers
226 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
9
votes
0answers
83 views

Finding an st-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path $P$ which minimizes ...
6
votes
0answers
66 views

Graph isomorphism problem for graphs with colored directed edges

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
6
votes
0answers
81 views

What is the proof for the lemma “For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge”?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
5
votes
0answers
81 views

Counting Graphs (Minimum Number of Bits Required To Encode Certain Graphs)

Background: I am interested in finding succinct data structures for certain types of graph classes, particularly partial k-trees. For general graphs, there are $\binom{\binom{n}{2}}{m}$ graphs on $n$ ...
5
votes
0answers
61 views

Decomposition of graphs that uses centers

Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason ...
5
votes
0answers
153 views

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a ...
5
votes
0answers
394 views

A variation in Ford-Fulkerson algorithm

Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow. I was thinking that when we augment a ...
5
votes
0answers
233 views

Worst-case sparse graphs for Hopcroft-Karp Algorithm

Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
5
votes
0answers
104 views

Beating fair colorings with few edges

I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can ...
5
votes
0answers
279 views

Kosaraju-Sharir algorithm and the inserted vertex

This is a question from my homework and I need some help. We are trying to run Kosaraju-Sharir algorithm over $G$, adirectional graph with arcs $(u,v)$. In the first DFS pass we inserted vertex $u$ ...
4
votes
0answers
52 views

Edge cuts with vertex weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over vertices (versus edge weights). I have looked at the literature but have not been able to find any ...
4
votes
0answers
66 views

Partition a bipartite graph to a complete matching and an independent set

I am looking for a reference for the following theorem: Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$). There is a nonempty subset $Y_1 ...
4
votes
0answers
272 views

Shortest path in graph - upgrade an algorithm

We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our ...
3
votes
0answers
117 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
3
votes
0answers
83 views

Graph partitioning problem

I am working on a solving a graph partitioning problem and have found a way to formulate it as a trace minimization. I am hoping this will allow me to relax the problem to a continuous one. I am ...
3
votes
0answers
49 views

Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof ...
3
votes
0answers
86 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
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. ...
3
votes
0answers
129 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 ...
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 ...
3
votes
0answers
82 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 ...
3
votes
0answers
914 views

Remove minimum number of vertices to disconnect the graph

Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink. My intuition tells me ...
2
votes
0answers
24 views

In case of a given graph , Is that possible to build trapezoidal map in linear time

[This regarding to Computational geometry in CS] Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G). I'd like to build a trapezodial map out ...
2
votes
0answers
40 views

Steiner tree wiring problem

I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner ...
2
votes
0answers
98 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
2
votes
0answers
38 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 ...
2
votes
0answers
267 views

Effect of increasing the capacity of an edge in a flow network with known max flow

I need your help with an exercise on Ford-Fulkerson. Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance. Now suppose you are ...
2
votes
0answers
76 views

Complexity of finding a subset of vertices within distance k of each other, given a set of vertices

I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
2
votes
0answers
54 views

End-Of-The-Line Augmented Problem of PPAD

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line: End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed ...
2
votes
0answers
58 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ ...
2
votes
0answers
93 views

Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each ...
2
votes
0answers
89 views

Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
2
votes
0answers
82 views

Graph conductance - program/code/library

Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing? Think it is quite well-known problem, ...
2
votes
0answers
699 views

Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
2
votes
0answers
56 views

IDS algorithm optimality for grid?

My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement. I read that the IDS algorithm is optimal, but in my case is not optimal ...
1
vote
0answers
59 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
1
vote
0answers
32 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
1
vote
0answers
29 views

How to maximize the number of buyers in a shop?

There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items ...
1
vote
0answers
145 views

Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
1
vote
0answers
152 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 ...
1
vote
0answers
53 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\}$, ...
1
vote
0answers
42 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 ...
1
vote
0answers
62 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 ...
1
vote
0answers
41 views

How to cluster nodes based on the number of dependencies

I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies. Dependencies can be thought of as number of edges ...
1
vote
0answers
44 views

Library for Maximum independent set on a sparse bipartite graph (from sparse matrix)

I am working with sparse matrices (not particularly huge, <100Mb) and I want to compute the largest independent set on the bipartite graph $(N,E)$ defined as follows: suppose the matrix is named ...
1
vote
0answers
54 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
1
vote
0answers
62 views

Graph estimation in high dimensional data

I am trying to estimate the graph in very high dimensional data, I mean with million nodes. Up to now all the papers that I have found, they are limited to few thousands. All of them like graphical ...
1
vote
0answers
71 views

Terminology for vertices in graph connecting vertices “in” and “outside of” a given component

Basically, I am looking for a (well-defined) term for some "borderline" vertexes interconnecting other vertices in and outside of a given connected component. More specifically, given directed graph ...
1
vote
0answers
30 views

Is it possible to discern the quality of web data from networks derived from it?

One topic I've recently looked at is co-occurence networks formed from Twitter tweets. This is how I felt after looking at the tweets of random people: This leads me to the question: Question: ...