Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
286
questions with no upvoted or accepted answers
6
votes
0
answers
246
views
Restricted Reachability Problem
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
- 800
5
votes
0
answers
93
views
Fine-Grained Hardness for Undirected Hamiltonicity
The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time.
However, for undirected graphs on $n$ nodes, there is an ...
- 484
5
votes
0
answers
179
views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
- 597
5
votes
0
answers
183
views
Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover
This problem came up in my study of digraphs:
Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$.
Note that $A$...
- 597
5
votes
0
answers
312
views
Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?
Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
- 51
5
votes
0
answers
86
views
Complexity of bounded degree full contraction
This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows:
Instance: A graph $G$ and two integers $d$ and $k$.
Question: Is there a ...
- 778
5
votes
0
answers
88
views
Series-parallel extension of a partial order respecting a given total order
Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.
An $O(n^3)$ ...
- 815
5
votes
0
answers
107
views
Optimal polynomial time algorithm to determine if a random graph is $k$-colorable
Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
- 451
5
votes
0
answers
83
views
Finding almost minimum cycle
Given an undirected unweighted graph, the almost minimum cycle is defined as the cycle whose length is greater than that of a minimum cycle by at most one. Itai and Rodeh in a seminal paper in 1978 ...
5
votes
0
answers
150
views
Online triangle counting
Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.
Given a graph $G$ and a collection $C$ of subsets of ...
- 829
5
votes
0
answers
120
views
The distribution on the solution space induced by randomized rounding
Consider the Goemans-Williamson algorithm for the MAX-CUT problem.
It is known, that if $maxcut(G) \geq 1-\epsilon$, then
the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
- 1,224
5
votes
0
answers
164
views
Indexing structure for all-pairs min-cuts in a huge DAG
I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution.
Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
- 8,811
5
votes
0
answers
130
views
Spectrum of absorbing random walk for regular graphs
I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as
\...
- 47
5
votes
0
answers
131
views
Why is it necessary to maintain a collection of forests in the dynamic graph data structure?
In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure ...
- 1,921
5
votes
0
answers
204
views
Standard reference for efficient computation of non-intersecting Eulerian circuit
A plane graph $G$ defines a cyclic ordering $O(v) = \langle v_1, v_2, \dotsc, n_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an ...
- 4,258
5
votes
0
answers
149
views
Computing diameter of a 3D polyhedron
A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$?
Or, maybe, some another common polyhedron representation would help fasten this?
- 151
5
votes
0
answers
359
views
Approximate c-chromatic number, each color class is P4-free (cograph)
The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
- 1,433
5
votes
0
answers
131
views
Is minimum weight simple cycles through specified vertics fixed parameter tractable?
The problem formulation is as follows:
Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$.
Parameter: $|S|=...
- 9,408
5
votes
0
answers
154
views
Union of two matching to maximize the number of cycles
Given $G$, $C$ and $M$, where $G$ is a graph with maximum degree $3$, $C$ is a hamiltonian cycle of $G$, and $M$ is a matching of $G$.
Let $\mathcal{N}$ be the set of all matching of $C$ with size $|...
- 4,367
5
votes
0
answers
1k
views
Fast algorithm for successively merging k-overlapping sets?
Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in ...
- 747
5
votes
0
answers
213
views
Minimum infeasible subgraph in assignment problem
Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. ...
- 51
5
votes
0
answers
106
views
Quantized Unbounded Flow
I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.
INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $...
- 1,100
4
votes
0
answers
92
views
Time Complexity of Pairwise Graph Connectedness
The Setup
Consider the following algorithmic problem which, for now, I will call $\mathsf{2GraphConnector}$.
Input: A natural number $|V|$, and a finite collection $\mathscr{E} = \left\{E_1, E_2, \...
- 41
4
votes
0
answers
169
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 484
4
votes
0
answers
86
views
Flipping one bit to maximize BMM output
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
- 1,177
4
votes
0
answers
993
views
Generating a random connected bipartite graph
A (n, m, k)-bipartite graph is a bipartite graphs with:
independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges
We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
- 141
4
votes
0
answers
210
views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
- 235
4
votes
0
answers
1k
views
Optimizing Maximum Weighted Matching (Edmonds Blossom)
Background:
I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:
https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java
The original Python implementation ...
- 231
4
votes
0
answers
302
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$...
- 322
4
votes
0
answers
154
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?
...
- 533
4
votes
0
answers
201
views
Graph Isomorphism of Strongly Regular Graph with fixed parameter
$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant.
Here,
$n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
- 533
4
votes
0
answers
93
views
Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs
Let $G=(V, E)$ be an undirected simple graph.
Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
- 650
4
votes
0
answers
277
views
Definition of Clique width of graph
The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations.
I would like to know why the name clique width is given to this definition. ...
- 2,004
4
votes
0
answers
1k
views
K-path cover problem for a DAG
I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the minimum k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with ...
- 41
4
votes
0
answers
63
views
Has there been any work done on incremental connectivity in path graphs?
This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental ...
- 1,921
4
votes
0
answers
202
views
Size of Independent set of sparse graphs with few triangles
Notations
$\alpha(G) = $ Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$,
$$\...
- 771
4
votes
0
answers
1k
views
Path finding algorithm to maximise points of interest along the route
I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point.
An user will enter the start location, the end location and the available time to travel. ...
4
votes
0
answers
142
views
Min Weight Complete bipartite subgraph
Suppose we are given a large bipartite graph with weighted edges, and a small parameter $d$ (e.g. $d$ is 3 or 4).
What is known about the run-time to find the minimum weight complete bipartite ...
- 1,327
4
votes
0
answers
663
views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
4
votes
0
answers
2k
views
Can the Hungarian method be used with real edge weights?
I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
- 161
4
votes
0
answers
96
views
Explicit combinatorial construction minimizing intersection of sets
I'd like to know if anything is known about the following problem:
Suppose we choose positive integer $t$ to be constant. Let $S = \{1,2,\dots,n\}$, where $n$ is sufficiently large. Consider a ...
- 41
4
votes
0
answers
267
views
Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two
It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
- 523
3
votes
0
answers
48
views
Linear-time maze exploration for finite automaton with pebbles?
Blum and Kozel have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may ...
- 31
3
votes
0
answers
49
views
Property testing algorithm for isomorphism to a balanced 3-sided complete graph
I am looking for testing algorithm in the dense graph model, that checks for a graph with $3n$ vertices whether it's isomorphic to a balanced 3-sided complete graph with $n$ vertices in each set. The ...
- 31
3
votes
0
answers
97
views
Cover all triangles of a graph with n subgraphs as small as possible
What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
- 63
3
votes
0
answers
72
views
Is there an algorithm for reducing the average row width of a sparse matrix?
Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be:
$$w_i \equiv r(A_i) - l(A_i),$$
where $r(A_i)$ is the index of the rightmost nonzero element ...
- 31
3
votes
0
answers
90
views
Approximative counting of matchings in a graph
The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
- 139
3
votes
1
answer
291
views
Dynamic transitive closure with immediate new reachability facts
The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, ...
- 361
3
votes
0
answers
54
views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
3
votes
0
answers
126
views
Minimum feedback arc set for dense directed graph
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
- 131