Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
2
votes
0answers
17 views
Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices
Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:
Their corresponding vertex induced subgraph has an even number of edges.
...
1
vote
0answers
20 views
Minimum shortest path cover of $n$ vertices in $R^m$
To optimize computational complexity of a class of manifold learning algorithms, I've encountered the minimum shortest path covering problem. Informally, we define minimum shortest path cover to be ...
3
votes
0answers
56 views
Approximation algorithm for finding the maximum common subgraph in two DAGs
Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the biggest subgraph that is common to both graphs. That is to find the biggest graph which is a subgraph of both $A$ and ...
2
votes
0answers
42 views
Determination of maximum number of incoming transitions to a state in any trace-equivalent representation of an LTS
Suppose $L$ is a labelled transition system (LTS). Suppose that the function $maxIn(L)$ (LTS $\rightarrow$ integer) returns the number of incoming transitions to the state of $L$ that has the most ...
5
votes
1answer
115 views
Does a chordal graph where the size of minimal separators is constrained have name?
An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains ...
-2
votes
0answers
17 views
Are all databases reducible to this ultimate abstract database design? [migrated]
I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
1
vote
0answers
83 views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
8
votes
1answer
80 views
Density of Ramsey Graphs
Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with ...
6
votes
0answers
146 views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
4
votes
1answer
80 views
Understanding the “gap theorem” in geometric spanners
I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:
Intuitively: A set of directed edges satisfies the gap property, if ...
3
votes
1answer
100 views
Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$
Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ ...
-5
votes
0answers
73 views
Show that Vertex-Cover is NP-complete, using Stable-Set [closed]
My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.
My approach: i know, Stable-Set is NP-complete, and all ...
5
votes
1answer
99 views
Number of edge induced subgraphs with given vertex parity
Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.
Questions
How hard is to compute $O$?
How hard is to compute the parity of ...
0
votes
1answer
82 views
directed or bidirected in relation to mssp (Multiple source shortest path)
Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed?
this is a picture of what I mean
The ...
2
votes
1answer
112 views
Problem understanding “connectivity” characteristic for the $k$-connected subgraph problem
I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw ...
4
votes
0answers
247 views
Multiple-sources dominator trees: compact representation and fast algorithm?
I recently learnt about the concept of dominator trees and was fascinated by it.
I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
0
votes
1answer
42 views
Designing a Transport network path suggestion tool
I am working on a suggestion system to passengers on transits to take.
The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent ...
0
votes
1answer
56 views
PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem
Problem 1
I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time ...
8
votes
1answer
1k views
Complexity of computing the average distance of a graph
Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$
One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum ...
16
votes
1answer
375 views
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute ...
0
votes
0answers
119 views
Generate TSP instances with known optimal
Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?
The idea is to be able to generating arbitrary large instances with known optimal ...
3
votes
0answers
249 views
Name this digraph
I am trying to track down the name of this digraph and some references:
You take all members of the transformation semigroup on $n$ elements, $T_{n}$.
For two members $x$ ,$y$ ; if $x$ is in the ...
3
votes
1answer
142 views
Approximating Bipartite Vertex Cover
Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover ...
1
vote
0answers
40 views
Help with the definition of clique percolation
So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph. However their image in Fig. 1 confuses me from the description.
As I ...
11
votes
2answers
536 views
Small graph with gap between chromatic and vector chromatic number?
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
3
votes
1answer
114 views
What is the fastest deterministic algorithm for incremental dynamic tree reachability?
As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.
...
3
votes
2answers
157 views
Generalization of independent set
I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices.
How about if you allow no more than $k$ pairs of adjacent vertices? ...
0
votes
0answers
45 views
DFS and c-Expander graph - simple path with the length of n-2c+1 [closed]
Just to make it clear - c-Expander graph is a directed graph G(V,E) with 2 Disjoint sets (A and B), of size equal or more than c with at least one Vertex between node of A and node of B.
I have to ...
1
vote
0answers
60 views
Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?
If we want a specific example, then how about the Erdos-Renyi random graph?
1
vote
0answers
129 views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
0
votes
0answers
56 views
Nonnegative Permanent and Ellipsoidal Method
Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.
This was based on the Ellipsoidal Method.
Finding a Max Cut is the same for Bipartite Graphs as ...
5
votes
1answer
113 views
Canonical labeling of special classes of DAGs
Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.
What are some special classes of DAGs that can be ...
4
votes
0answers
99 views
Bipartite vertex separator
Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph?
I have a ...
1
vote
1answer
83 views
Max flow with conditional edges
Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?
Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.
3
votes
1answer
148 views
Breadth first search and Eppstein K shortest paths algorithm
I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
I have trouble particularly ...
6
votes
0answers
72 views
Increasing the capacity to maximize the min cut
Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.
Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging ...
4
votes
1answer
100 views
Adjacency-Preserving 2D Grid Embedding
Consider a 2D grid, and a given planar graph $G$ with $\Delta<4$ (max node degree) and without odd cycles. What conditions should $G$ satisfy so that when it is mapped (or embedded) into the 2D ...
7
votes
1answer
130 views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.
...
18
votes
1answer
333 views
Is induced subgraph isomorphism easy on an infinite subclass?
Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem
Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?
is ...
1
vote
0answers
47 views
Generalization of hyperbolicity of graphs
Given a graph G together with the usual shortest-path metric defined on it, dG : V (G) × V (G) -> {0, 1, 2, 3, . . .}, we can associate Gromov hyperbolicity as a measure of tree-likeness. Practically ...
6
votes
1answer
148 views
Finding appropriate spanning tree of connected bipartite graph
I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?
Problem: We have a connected ...
1
vote
2answers
253 views
Variation on longest path in a DAG
Consider a directed acyclic graph with $n$ nodes and $m$ edges. Each edge is assigned a positive weight. There is a start node $s$ and an end node $e$. We want to find the path from $s$ to $e$ that ...
6
votes
0answers
90 views
N shortest tours in a graph
I'm searching for papers dealing with the problem of finding not just the shortest tour in the graph (TSP) but finding N shortest tours. Somewhat surprisingly, I didn't find any mention of it, ...
-4
votes
2answers
105 views
Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially? [closed]
Let us assume (probably wrongly) that P=NP, meaning that we know a way to output a hampath if it exists.
A graph has $n$ vertexes.
Can the algorithm that solves the problem be modified in ...
1
vote
0answers
81 views
What is the shape of cost function of weighted graph matching problem?
According to Umeyama, the weighted graph matching problem can be formulated as
$min_P || PA_GP^T - A_H ||$
s.t. $P$ is a permutation matrix.
where $A_G$ and $A_H$ are n-by-n matrices
If we relax ...
6
votes
2answers
192 views
Caterpillar decomposition of trees
Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the ...
3
votes
0answers
99 views
Linear programming - How to allow cycles with weight at most s?
Consider a graph $G=(V,E)$ with nonnegative weight function on the edges $w$.
How would you express in LP that you want to allow cycles in $G$ with total weight at most $s$ ?
I've found this while ...
3
votes
1answer
137 views
How can we derive this lower bound of a special cut in a graph?
I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
0
votes
1answer
60 views
Source sending 0 transport units
I have a network flow (with min and max capacities) where the only transport units flowing are within a cycle (of flow value 2). The source of the network does not send out any transport units into ...
13
votes
1answer
287 views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a ...
