All Questions
127 questions
1
vote
1
answer
46
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 ...
- 111
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
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
CommunityBot
- 1
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=...
CommunityBot
- 1
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 ...
47
votes
15
answers
29k
views
What are the applications of hypergraphs?
Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
- 35.5k
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 ...
- 82.7k
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
2
votes
1
answer
252
views
Size of forbidden minors for treewidth
For any $k$, the class of graphs of treewidth at most $k$ can be characterized by a finite set of forbidden minors.
For treewidth $1$ and $2$, the set is of size $1$. Then for treewidth $3$, the set ...
- 32.1k
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 ...
- 183
5
votes
1
answer
291
views
Minimum number of edges to remove to have low degree
I have the following problem, where $k$ is a fixed integer.
Input: Graph $G$.
Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.
Do ...
- 32.1k
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). ...
- 131
9
votes
3
answers
2k
views
Are regular graphs the hardest instance for graph isomorphism?
Regular graphs are the graphs in which the degree of each vertex is the same. The Weisfeiler-Lehman algorithm fails to distinguish between the given two non-isomorphic regular graphs.
Is there a ...
- 25.4k
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 ...
- 7,226
3
votes
2
answers
404
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...
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 ...
CommunityBot
- 1
7
votes
2
answers
827
views
Graph minor check
Are there any good algebraic/algorithmic tools available to check if a given graph $H$ is a minor of $G$ from the adjacency matrix of $G$?
- 4,713
17
votes
9
answers
3k
views
Where on the internet I can find a database of graphs?
I am studying graph algorithms.
I need a database of graphs on which I can test my algorithms.
Where can I find a reliable database of graphs of all kinds?
Thanks!
- 225
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 \...
- 37.7k
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 ...
- 32.1k
33
votes
3
answers
3k
views
Can assignment solve stable marriage?
This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy.
Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
- 1,446
4
votes
1
answer
1k
views
Polygamous stable marriage/ assignment problem
I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
CommunityBot
- 1
3
votes
0
answers
370
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 ...
- 63.9k
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 (...
- 12.9k
5
votes
1
answer
348
views
Reachability in digraphs
I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.
I'm aware of "A fully dynamic data structure for reachability in ...
- 1,446
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 ...
CommunityBot
- 1
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 ...
- 32.1k
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 ...
- 9,720
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$ ...
- 241
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.
...
- 17.9k
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
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, ...
- 32.1k
2
votes
1
answer
181
views
What is the relation between size of maximum clique and branchwidth?
Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds:
$$
\omega(G)\leq bw(G)
$$
Intuition: Assume (in reverse of ...
- 32.1k
9
votes
3
answers
2k
views
Embedding planar graphs into the grid
I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
- 32.1k
6
votes
4
answers
552
views
(Non)uniqueness of the common-factor graph
Let $S=\{x_1,\ldots,x_k\}$ be a set of $k$ distinct natural numbers,
a subset of $\{1,\ldots,n\} = \mathbb{N}_{\le n}$.
Define the common-factor graph $G(S)$ as the (undirected) graph with
a node for ...
- 32.1k
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
5
votes
1
answer
274
views
Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?
I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...
- 32.1k
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
24
votes
2
answers
2k
views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
- 32.1k
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(...
- 32.1k
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
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 ...
- 32.1k
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 ...
- 1,701
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 ...
- 3,065
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 ...
- 5,429