Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
956
questions
1
vote
1answer
90 views
Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?
Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?
I read abstract of this paper that mentioned an algorithm with running ...
2
votes
1answer
92 views
exact path cover for undirected graph
In a Python plotting application,
I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path.
The number of ...
5
votes
0answers
71 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 ...
1
vote
0answers
78 views
+100
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$ ...
2
votes
0answers
75 views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
1
vote
1answer
153 views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
0
votes
0answers
48 views
Minimal lexicographical path on DAG in O(||V| + |E|)
Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest ...
2
votes
1answer
72 views
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Consider the node-weighted steiner problem:
Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \...
4
votes
1answer
256 views
Pagerank in directed *acyclic* graphs (DAG)
I deal with pagerank computations on large directed acyclic graphs (DAG).
I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
2
votes
0answers
88 views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
0
votes
0answers
101 views
Does this sum-product algorithm make more sense?
Recall the belief propagation "sum-product" algorithm (from wikipedia):
$\forall x_v\in Dom(v),\;$
$\mu_{v \to a} (x_v) = \prod_{a^* \in N(v)\setminus\{a\} } \mu_{a^* \to v} (x_v)$
$ \mu_{...
6
votes
0answers
140 views
Fastest exact algorithm for MAXCUT
Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA
Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
4
votes
2answers
224 views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
1
vote
1answer
92 views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
1
vote
0answers
42 views
Prune length distribution of random binary tree
Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
3
votes
1answer
96 views
Finding the single-crossing embedding of a single-crossing graph
Is it known how to find a (piecewise) straight-line embedding of a single-crossing graph on the plane with exactly one crossing in polynomial time? We are currently trying to come up with a method for ...
2
votes
1answer
148 views
Coloring intersection graph of squares
It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard.
What about squares and more specific case "unit squares"?
Thanks.
-1
votes
1answer
230 views
Find research partner (profession and beginner)
I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program.
Now, I've ...
10
votes
0answers
274 views
Finding uniformly random perfect matching of a graph
Problem: Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
3
votes
1answer
131 views
Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$
For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...
3
votes
1answer
149 views
TSP with "enemy" nodes
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea ...
4
votes
0answers
82 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
vote
1answer
108 views
Finding output with unique witness in matrix multiplication
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication ...
8
votes
1answer
133 views
Finding vertex separator such that the induced subgraph has minimal number of edges
My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
0
votes
0answers
51 views
Efficiently checking if removing a vertex yields a connected partition
Having seen the answer here, I have been looking at the algorithm suggested by Chlebikova (1996). The algorithm needs an implementation of the blockbalance algorithm which requires that one repeatedly ...
4
votes
1answer
175 views
Does such a bipartite graph exist?
In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
1
vote
0answers
31 views
Latest results on the k-stacker crane problem?
I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the ...
1
vote
0answers
47 views
Generalizing PageRank for tripartite graphs
Problem
I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...
3
votes
1answer
97 views
Approximating Independent Dominating set on bipartite graphs
I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.
My question is: are there any positive results in the ...
2
votes
0answers
97 views
Graph recovery from pairwise-common neighborhoods
Define the common neighborhood of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the pairwise-common ...
1
vote
2answers
130 views
Maximum cliques of the transitive closure of a chordal DAG
Let $G=(V,A)$ be a directed acyclic graph, for which the underlying
undirected graph is chordal (so that every induced cycle in the
underlying undirected graph is a triangle).
It is known that in a ...
5
votes
0answers
151 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 ...
7
votes
1answer
293 views
STCONN in $O(n)$ time?
This is a very basic question on $s$-$t$-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph $G=(V,E)$ in $O(n+m)$ time and $O(n)$ space, where $n=|...
1
vote
1answer
49 views
Bipartite graph projections, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
2
votes
1answer
34 views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a ...
6
votes
2answers
369 views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
5
votes
1answer
245 views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
2
votes
0answers
168 views
Is this node permutation optimization NP-Hard?
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
2
votes
0answers
81 views
Dynamic connectivity with known history, for maximal connected component span
Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
5
votes
0answers
169 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$...
1
vote
2answers
105 views
Name of this graph partitioning problem? (related to coloring)
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
3
votes
1answer
55 views
Problem conditions to use Laplacian solvers
I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.
Suppose that we want to solve Ax=b, ...
2
votes
0answers
30 views
Pagerank update upon vertex removal
Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges.
How to efficiently compute the Pagerank of remaining vertices in the ...
3
votes
1answer
154 views
A stronger Flow Decomposition Theorem?
In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:
Every nonnegative arc flow x can be represented as a path ...
9
votes
1answer
194 views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
-1
votes
1answer
36 views
Multi agent path following with collision avoidance with pre-determined path
I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only.
The problem:
There is 12x12 grid, with a few solid blockades within them....
0
votes
0answers
29 views
Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph
tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
1
vote
1answer
120 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, ...
3
votes
1answer
113 views
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
2
votes
1answer
72 views
Has this bipartite graph problem been studied?
I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon ...
