All Questions
Tagged with graph-theory algorithms
112 questions with no upvoted or accepted answers
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
12
votes
0
answers
1k
views
Shortest path in Cayley graphs
The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...
- 121
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
7
votes
0
answers
186
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
- 37.7k
6
votes
0
answers
65
views
Vertex cover in bipartite graphs with bounds on cost and size
Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
- 96
6
votes
0
answers
620
views
Detect cycle in graph in logspace and linear time?
Let's consider graphs of bounded degree.
I know that it's possible to detect cycles in a graph in linear time -- essentially do a depth-first search, depositing a trail along the path you're currently ...
- 2,519
6
votes
1
answer
534
views
How to find the Eulerian circuit with the minimum accumulative angular distance within an Eulerian graph?
Note: I originally posed this question to Mathematics, but it was recommended that I try here as well.
Context
For context, this problem is part of my attempt to determine the path of least inertia ...
- 161
6
votes
0
answers
69
views
Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time
A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...
- 37.7k
6
votes
0
answers
315
views
Algorithms for computing the Resilience of Graphs
The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
- 903
6
votes
0
answers
172
views
Uniformly sampling from the set of all simplicial maps
Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial maps ...
- 15.5k
5
votes
0
answers
244
views
When does a "stable" assignment of buyers into goods exist?
Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
- 618
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 3,475
4
votes
0
answers
204
views
Enumeration of stable graphs of genus $g$
Let $G=(V,E)$ be a connected undirected finite graph, let us call $G$ stable if each vertex has degree at least $3$.
Is there a computer algorithm to efficiently enumerate (repetition allowed) all ...
user39380
4
votes
0
answers
207
views
Disjoint paths in temporal graphs
Given a graph $G=(V,E)$ and a pair of source-destination nodes $s$ and $t$. Time is divided in periods with the total number of periods denoted by $T$. Each edge $e$ is either operational or broken at ...
- 367
4
votes
2
answers
381
views
Max weighted matching where edge weight depends on the matching
Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
- 367
4
votes
0
answers
94
views
Efficient algorithm to construct path augmented graphs with smallest diameter?
I am interested in special graph constructions that have the smallest diameter. We have a path graph $P_n$ ($N$ is even). We add new set of edges $C$ between path nodes such that set $C$ forms a ...
- 2,993
4
votes
0
answers
175
views
What is known about the complexity of this covering problem?
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
- 2,966
4
votes
0
answers
220
views
Navigation in a graph
The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...
- 323
4
votes
0
answers
209
views
Rough structure of the double coset space/Graph bijections up to automorphisms
I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...
- 679
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
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
3
votes
0
answers
254
views
Algorithm for regular graphs of tessellation {p,q}
We consider a particular class of tessellations $\{p,q\}$ on a Poincaré disk. There are few examples where a regular graph for a particular tessellation has been obtained. It is done by identifying ...
- 81
3
votes
0
answers
88
views
Infection on a complete graph
Suppose we have a complete graph on $2n$ vertices with one "infected" vertex.
At each time step, we form a matching of the vertices. Then the vertices paired with infected vertices will also ...
3
votes
0
answers
56
views
Karp hardness of two cycles which lengths differ by one
Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is it $NP$-...
- 121
3
votes
0
answers
40
views
Constructing a graph with a given number of edges and a given triangle distribution
Give a number of edges $|E|$, number of vertices $|V|$ and a $|V|\times 1$ vector of integers $T=[t_1, \cdots, t_{|V|}]$, I wish to construct an undirected graph with $|V|$ vertices, $|E|$ edges such ...
- 503
3
votes
0
answers
111
views
Is there a Havel-Hakimi for geometric graphs?
Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this?
...
- 18.9k
3
votes
0
answers
57
views
Algorithm to construct metric space endomorphism with controlled square
Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be $K$-...
- 15.5k
3
votes
0
answers
350
views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
3
votes
0
answers
280
views
Additional Constraint Baum Welch for HMMs
I'm trying to derive a special form of the Baum Welch algorithm where there is an additional constraint that the sum of emission probabilities over all states sums to one for each output symbol. ...
3
votes
0
answers
620
views
Graph recognition software
ISGCI lists a lot of graph classes, many of which are recognizable in polynomial time. Is anyone here aware of actual implementations of these algorithms?
- 1,164
3
votes
1
answer
3k
views
Fast algorithm for counting the number of acyclic paths on a directed graph
In short, I need a fast algorithm to count how many acyclic paths are there in a simple directed graph.
By simple graph I mean one without self loops or multiple edges.
A path can start from any node ...
- 911
2
votes
0
answers
135
views
Minimum cost k-edge connected subgraph
The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
- 21
2
votes
0
answers
54
views
Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?
I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...
- 161
2
votes
0
answers
106
views
Decomposing a planar graph
Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
- 3,153
2
votes
0
answers
79
views
Pagerank Markov chain reductions
In short: if a Markov chain models a (generalized) pagerank, is it always possible to remove any of its state and obtain a Markov chain that models a pagerank close to the initial one?
Full details.
...
- 1,444
2
votes
0
answers
69
views
Are two degree sequences compatible, for random simple graph generation?
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
2
votes
0
answers
388
views
A fast algorithm for deciding if a given undirected graph contains a C4 subgraph
I'm looking for an algorithm for deciding if a given undirected graph G contains C4 as a sub graph, not necessarily induced. I'm not interested in finding such a cycle, if it exists.
I was told there ...
- 21
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 13.2k
2
votes
0
answers
65
views
The best way for obtaining the canonical label of a matroid?
For a graph, we can canonical labelings with Nauty or other methods. But for a matroid, I do not find an easy way to labeling.
Dillon Mayhewa, Gordon F. Royle introduced the hyperplane graph of a ...
- 51
2
votes
0
answers
48
views
Planarity of a subgraph
Given a complete symmetric graph $G(V,E)$ with real-valued edgeweights and assume that every induced $k_4$ that is induced by a quadruplet from $v$'s vertices has a unique perfect matching of maximal ...
- 13.2k
2
votes
0
answers
288
views
3-uniform hypergraphs and their circuit space
So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
- 21
2
votes
1
answer
329
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 13.2k
2
votes
0
answers
162
views
Calculating Minimum Spanning Trees in Very Big Graphs
I need to determine Minimum Spanning Trees (MST) of very big complete graphs, whose edgeweights can be calculated from data that is associated with the vertices.
In the planar euclidean case, for ...
- 13.2k
2
votes
0
answers
27
views
Complexity of weighted fractional edge coloring
Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $...
- 151
2
votes
0
answers
520
views
Succinct circuits and NEXPTIME-complete problems
I am fascinated by a recent fact I was reading: Succinct Circuits are simple machines used to descibe graphs in exponentially less space, which leads to the downside that solving a problem on that ...
- 41
2
votes
0
answers
76
views
Fastest Algorithm to calculate Graph pebbling number?
I am interested in Graph Pebbling, and in particular what are the fastest known algorithm is to find the pebbling number of a graph. Also, i am interested whether there are lower limits on the runtime ...
- 41
2
votes
0
answers
228
views
Known Methods for "Mutexing" Antiparallel Arcs in Graphs
I recently faced the problem of calculating shortest paths in undirected graphs in the presence of negative edge weights; I could not find any applicable algorithms via online search.
Transforming the ...
- 13.2k
2
votes
0
answers
110
views
Does there exist a linear-time algorithm to find a basis of the null space of the adjacency matrix of a tree?
I am working on a decomposition of trees based on the null space of the adjacency matrix of the tree. Most algorithm on trees are really fast. The decomposition could give some algorithms to find ...
2
votes
0
answers
120
views
Blossoms and Colorings
There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
- 13.2k