Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,283
questions
2
votes
0answers
81 views
What can i learn about a graph about which only certain properties are known [closed]
1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts?
The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable,
The degree of each ...
5
votes
1answer
363 views
Connectivity of a random regular graph of degree $d$
An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? ...
2
votes
1answer
161 views
Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
2
votes
0answers
151 views
Computational Complexity of cycle double cover
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
-1
votes
1answer
110 views
Multiple source shortest path with one reversal [closed]
Lets say we have a directed graph G, with vertices V, that have lengths l.
I need to find the shortest path between every ordered pair of vertices in the graph, with the following constraint:
In a ...
2
votes
0answers
186 views
zero-sum path problem on a digraph
Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the ...
2
votes
0answers
204 views
Graph optimization problem with multiple objectives/constraints
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We can divide vertices in ...
4
votes
1answer
405 views
Proof that the graph optimization problem is NP-hard
I'm trying to prove that the following optimization problem is NP-hard:
Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
-2
votes
1answer
212 views
questions on implications Babais quasi P time graph isomorphism result
Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs.
based on the proof, does this mean now that if Johnson ...
1
vote
1answer
318 views
What is a weakly-simplicial vertex?
While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded.
A ...
6
votes
2answers
502 views
Has this generalization of the vertex cover problem been researched?
I have the following problem, let's call it the $n$ vertex cover:
Given a directed graph $G,$ find a minimum subset of vertices $S$ such that each trail of length $n$ has at least one vertex in $S$....
2
votes
1answer
255 views
Partition refinement in transition state systems (bisimulation contraction)
I am trying to understand bisimulation contraction of Kripke models.
I have read these lecture slides and this Wikipedia page, but I still don't fully understand it.
I can understand that the two ...
4
votes
2answers
162 views
Complexity of Uniform Generation of Perfect Matchings
Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to ...
1
vote
0answers
177 views
Maximize the weight of MST + sum of vertex weights
I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
11
votes
1answer
299 views
Generalization of Dilworth's theorem for labeled DAGs
An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth'...
7
votes
0answers
87 views
Complexity of computing the simplicial width of a graph
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:
For every edge $\{v_1,v_2\} \in E$, there ...
0
votes
1answer
94 views
Number of bounded minimum vertex covers
Minimum Vertex Cover problem
Input: $G=(V,E)$ and Parameter $k$
Output: Decide whether there exists minimum vertex cover of size at most $k$.
Question:-
Can we bound the number of minimum vertex ...
3
votes
1answer
112 views
Shortest cycle separator for biconnected planar graphs
An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is ...
8
votes
1answer
175 views
What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?
In this paper, Hajnal states the following lemma:
Let $\mathscr{G}_{n, m}$ be the set of all bipartite graphs with $n$ vertices in the left part and $m$ vertices in the right part. Suppose $\...
2
votes
1answer
405 views
Max weight k-clique
Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however ...
10
votes
2answers
604 views
Are social networks typically good expanders?
I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility ...
2
votes
0answers
311 views
expected number of edges for fixed min cut
It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.
Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
8
votes
1answer
354 views
Bipartite matching with degree domination
Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $...
3
votes
1answer
141 views
Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K
I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.
The ...
6
votes
0answers
163 views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
9
votes
0answers
314 views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
4
votes
0answers
139 views
Graph Isomorphism Algorithm of Vertex Transistive Graphs and other
What are the best known Graph-Isomorphism algorithms for below graph classes-
1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive.
Are they GI Complete?...
1
vote
1answer
125 views
K-fold Traveling salesman problem - A variant of TSP
Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^...
1
vote
1answer
934 views
Longest path from every vertex in a tournament
I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path ...
1
vote
0answers
1k views
Fastest Algorithm for the Minimum Edge Covering Problem
Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:
G' must include all the ...
1
vote
0answers
169 views
What is the *generally accepted* definition for the percolation threshold on finite-sized graphs?
For "regular" graphs (lattices, if you will), it's easy to define the percolation threshold $p_c$ as the critical probability beyond which the infinite graph will contain an infinitely large cluster ...
3
votes
1answer
209 views
Finding a graph that minimizes the number of nodes for a given number of paths
There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting ...
1
vote
0answers
98 views
Detecting bridges in Hypergraph S-t Reachability
Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
3
votes
0answers
134 views
Maximize number of edges covered by an independent set of vertices
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
8
votes
2answers
723 views
Dichotomy of the spectra of directed graphs
Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:
It is known that a directed graph $G = (V,E)$ has an adjacency ...
4
votes
1answer
887 views
Smallest vertex cover which is also an independent set
The vertex cover and independent set as a subset of nodes are always considered in a dual relationship. Have they been looked at together? What I mean is: start from a minimum vertex cover, and if it ...
1
vote
0answers
94 views
Concentration Bounds for functions of matrices
This is a question about properties of large directed graphs which are preserved when we randomly sample edges.
Imagine I have an infinite sequence of positively weighted directed graphs. The ...
2
votes
1answer
248 views
generate a graph with fixed min cut
Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to ...
7
votes
1answer
296 views
Minimum Spanning tree on a complete “random” graph
Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
2
votes
1answer
267 views
Are there any results on the following “generalized matching” problems?
Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic ...
1
vote
1answer
83 views
Subclasses or characterizations of modular or pseudo-modular planar graphs
We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined ...
8
votes
1answer
288 views
Are there poly time algorithms to determine if a graph is almost bipartite?
Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.
Are there poly time algorithms to determine if a graph is exactly or ...
4
votes
1answer
136 views
What automorphisms on a Markov Chain imply a uniform limiting distribution?
Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various ...
6
votes
1answer
103 views
Is every well-founded simplification order a well-partial order?
I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing ...
8
votes
2answers
200 views
Something-Treewidth Property
Let $s$ be a graph parameter (ex. diameter, domination number, etc)
A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{...
4
votes
2answers
459 views
Does the problem “partition a vertex-weighted graph into $k$ balanced connected parts” have a standard name?
Consider the following problem:
Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
12
votes
2answers
191 views
Reference for a class of graphs that preserve subgraph distances when ordered
Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v_1, v_2, \ldots v_n$ in such a way that the graph $H_i$ induced by the vertices $\{v_1, \ldots, v_i\}$ has $dist_{H_i} ...
4
votes
1answer
157 views
Bidirectional A*: is an update of the distance estimation feasible while searching?
The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal.
The ...
2
votes
1answer
205 views
Intersection graphs of squares and rectangles
Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)?
0
votes
1answer
123 views
The number of edges in the ith shortest path in a directed graph
$G$ - directed graph,
$n$ - count of nodes
According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges.
Anybody can explain how this estimate is ...
