All Questions
127 questions
1
vote
1
answer
45
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 526
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
0
votes
0
answers
69
views
What is the complexity of computing isomorphism of two non-regular graphs?
Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
- 101
10
votes
4
answers
662
views
Deciding homomorphic images of De Bruijn graphs
The De Bruijn graph $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put ...
- 105
1
vote
0
answers
76
views
Constructing orientations that increase (directed) distances between vertices in a maximum independent set
An orientation of a simple undirected graph $G=(V,E)$ is a directed graph $G' = (V,E')$ that is constructed by including either $(u,v) \in E'$ or $(v,u) \in E'$, but not both, for all $(u,v) \in E$.
...
- 73
2
votes
1
answer
482
views
Counting $n$-edge directed graphs
I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...
- 21
2
votes
1
answer
170
views
Is there an algorithm to generate non-isomorphic Halin graphs?
A Halin graph is a graph constructed by embedding a tree with no vertex of degree
two in the plane and then adding a cycle to join the tree’s leaves.
We found a list of the number of Halin graphs ...
- 1,851
0
votes
2
answers
251
views
Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)
Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...
- 143
1
vote
2
answers
223
views
Do all graphs with $n$ vertices and $m$ edges have a special property?
Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.
For which values of $n$ and $m$ does the following requirement hold:
$\forall G \in \...
- 1,000
3
votes
1
answer
241
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 33
3
votes
0
answers
369
views
Perfect matching decomposition algorithm for bipartite regular graphs
It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is ...
- 51
1
vote
0
answers
52
views
How can we hang the weighted trees so that vertices nearer to root (based on distances, not hop count) lie in upper levels?
I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...
1
vote
1
answer
744
views
Efficient algorithm for edge-coloring complete graphs
Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
- 1,190
6
votes
3
answers
1k
views
Algorithm to calculate edge orbits of a graph
Vertex orbits are a well-known concept in Graph Theory: these are the equivalence classes of vertices under the automorphism group $Aut(G)$ of a graph $G$. In the example, circled vertices are ...
1
vote
1
answer
71
views
Steiner tree subject to edge capacity constraint
Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ ...
- 367
1
vote
1
answer
220
views
Construct a rooted plane tree with nodes labelled
A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.
...
- 1,190
1
vote
1
answer
134
views
A variant of min-cost flow problem
Given a flow $f$ in graph $G$. For each node $v\in G$, we call the edges ajacent to $v$ containing non-zero quantity of flow as $v$'s active edges. My problem is to find a min-cost flow under the ...
- 367
1
vote
0
answers
64
views
A variant of node-disjoint path problem
Given a graph $G$, I want to find $2$ (or $k$) node-disjoint paths with minimum total cost (or minimum maximum cost). The problem is a classical problem, but I have the following non-trivial setting. ...
- 367
3
votes
0
answers
280
views
Max flow with minimum number of edges
A max-flow problem may have multiple solutions. Among these max-flows, I seek the one with the minimum number of positive flow edges (by positive flow edges I mean the edges carrying positive flow). ...
- 367
1
vote
1
answer
97
views
A sufficient condition for a subcubic graph having a 2-distance vertex 4-coloring
Let $G$ be a subcubic graph with only vertices of degree 1 or degree 3.
Suppose that $G$ has an edge coloring $\varphi$ using colors from $\{1,2,3,4,5\}$ such that
each edge is colored with a set of ...
- 557
2
votes
1
answer
120
views
$W[1]$-hard and FPT about the equitable tree-coloring problem
I am confused by the two conclusions in this paper (DOI link behind paywall at Springerlink).
It shows that the equitable tree-coloring problem is $W[1]$-hard when parameterized
by treewidth.
However, ...
- 91
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
1
vote
1
answer
204
views
Coloring infinite graph made out of copies of a finite graph
I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically:
Vertex set of $G^\infty$ is $$V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(...
- 119
2
votes
1
answer
94
views
What is the complexity of a special multigraph edge coloring problem
Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at ...
- 1,190
0
votes
0
answers
36
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
- 171
1
vote
0
answers
168
views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
- 1,190
2
votes
1
answer
156
views
Directed version of this lemma
On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
- 71
2
votes
1
answer
153
views
Min-sum and min-max node-disjoint path problems
Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
- 367
0
votes
1
answer
170
views
Find cycles with specific weights in complete graph
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique ...
- 11
1
vote
0
answers
61
views
Algorithm for minimum weight matching with "tree topology"
Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...
- 13.2k
0
votes
0
answers
59
views
A variant of travel salesman problem with charging points
Given a graph composed of a set $V$ of nodes, each representing a point to be visited by a salesman, and a set of fixed charging points. The salesman disposes a car that can travel $D$ distance before ...
- 367
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
1
vote
0
answers
74
views
Reduction maximum independent set to MIS in a very dense graph
We got a reduction maximum independent set to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G$ be graph of order $n$ and ...
- 25.4k
1
vote
0
answers
177
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
1
vote
0
answers
149
views
Minimum delay path in time-dependent graph
Given a time-dependent graph, where each edge $e$ is on for certain time intervals and off otherwise. Traversing $e$ incurs a delay $d_e$ and is possible only when $e$ is on. Given a pair of vertices $...
- 367
0
votes
2
answers
183
views
Minimal bottleneck path in time-varying graph
Given a graph $G=(V,E)$. The cost of each edge $e$ is a function of time, denoted by $w_e(t)$. Given a time interval $[0,T]$, for any path $P$ starting at $v_s$ at time $t\in[0,T]$, we denote $t_e^P$ ...
- 367
0
votes
0
answers
116
views
Procedure to color the edges of a circulant graph
From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
- 2,089
2
votes
1
answer
54
views
Uniform closure of a neighbourhood complex in the tritetragonal tiling
Consider a neighbourhood complex of eight vertices (red) with vertex configuration $(3.4)^3$ which gives rise to the tritetragonal tiling of the hyperbolic plane:
Not knowing if this complex can be ...
- 9,720
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 343
10
votes
2
answers
595
views
Transfinite algorithms
The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
- 32.1k
3
votes
2
answers
898
views
Finding a cycle of a specific length in an edge-weighted graph
I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.
For example, imagine my phone tells me that I need to walk three miles today. It ...
- 151
2
votes
1
answer
55
views
maximum weighted matching with weights being sets
Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
- 367
4
votes
1
answer
672
views
Algorithm to generate free unlabelled trees uniformly at random
I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
5
votes
1
answer
320
views
Complexity of graph 3 coloring and counting algorithm
3-coloring a graph $G$ is equivalent to partitioning the
vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$
is the order of $G$.
We have $G \...
- 25.4k
0
votes
1
answer
114
views
Recognition of a graph as a product of its quotients
Is there an algorithm to determine whether a given simple graph $G$ is a product graph, typically, say a cartesian product graph of two smaller simple graphs $G_1, G_2$, such that the two simple ...
- 2,089
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 1,677
1
vote
3
answers
6k
views
Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?
I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher ...
- 475
1
vote
0
answers
82
views
Treewidth problem equivalence
Say we are solving a tree decomposition problem, e.g.
given a graph $G = (V, E)$ we try to find a chordal graph $H$ such that $V(H) = V(G)$, $E(G) \in E(H)$ and the maximal clique in $H$ is minimal ...
- 71
0
votes
3
answers
308
views
Clustering on tree
I am looking for a method that would identify clusters in a tree-like structure. In the figure below you can see a very simple example where one can visually identify distinct branches with a lot of ...
- 237