Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

230 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
96 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 $...
5
votes
0answers
81 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
0answers
131 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 ...
5
votes
0answers
115 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}$...
5
votes
0answers
154 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 ...
5
votes
0answers
125 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 \...
5
votes
0answers
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 ...
5
votes
0answers
173 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 ...
5
votes
0answers
146 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?
5
votes
0answers
186 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 ...
5
votes
0answers
127 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|=...
5
votes
0answers
150 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 $|...
5
votes
0answers
988 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 ...
5
votes
0answers
208 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$. ...
5
votes
0answers
103 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 $...
4
votes
0answers
196 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)$ ...
4
votes
0answers
959 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 ...
4
votes
0answers
141 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? ...
4
votes
0answers
191 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 ...
4
votes
0answers
91 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 ...
4
votes
0answers
249 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. ...
4
votes
0answers
916 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 ...
4
votes
0answers
60 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 ...
4
votes
0answers
180 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$, $$\...
4
votes
0answers
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
0answers
134 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 ...
4
votes
0answers
597 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
0answers
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 ...
4
votes
0answers
93 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 ...
4
votes
0answers
260 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 ...
3
votes
0answers
102 views

Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
3
votes
0answers
65 views

Uniformly sampling or counting connected graph partitions with any number of blocks

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ...
3
votes
0answers
41 views

Incremental PDA emptiness testing?

Is there anything known about the problem of incremental emptiness testing for a pushdown automata? Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
3
votes
0answers
147 views

Enumerating Minimal (a,b) vertex separators in a DAG

A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components. $S$ is a ...
3
votes
0answers
56 views

Algorithms for Maximum weight connected subgraph in planar graphs

I wonder what is known about the two following maximisation problems. Maximum weight connected subgraph : Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$ Output :...
3
votes
0answers
341 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 ...
3
votes
0answers
107 views

Graph-related applications of the fast Fourier transform (and other algebraic algorithms)

The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths). However, while the fast Fourier transform algorithm implies several other near-...
3
votes
0answers
140 views

Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem

Suppose we are given a standard first-order unification problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal ...
3
votes
0answers
102 views

Restricted k-set cover is in NL or L

Restricted $k$-set cover: Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$. Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\}, i_1=min(S_1),i_2=...
3
votes
0answers
90 views

Maximum weight triangles in dense graphs

There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs. Several of these ...
3
votes
0answers
239 views

Equivalence of deterministic finite transducers over finite/infinite words

Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is decidable whether a transducer is single-valued. Note that two ...
3
votes
0answers
255 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
3
votes
0answers
155 views

Multi-Agent Pathfinding

Quoting from Wang and Botea 2011: An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $...
3
votes
0answers
471 views

Broadcasting in node-weighted graphs

Given an undirected graph $G=(V,E)$ with non-negative node-weights $\text{w}(v)$, $v \in V$, I want to find a spanning tree $T$ of $G$ with minimum "cost" $\text{w}(T) = \sum_{v\in V} \deg_T(v)\cdot ...
3
votes
0answers
489 views

Is there a tight lower bound on the complexity of SSSP on a graph?

I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
3
votes
0answers
194 views

Randomized rounding on a graph

Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint: \...
3
votes
0answers
75 views

Load-balancing; Alternate methods of keeping track of nodes?

Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network. One popular method uses virtual-...
3
votes
0answers
152 views

Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints

Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of ...
3
votes
0answers
606 views

K-shortest path in large sparse graph

I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of ...
3
votes
0answers
185 views

Separation Oracle for Inverse Bipartite Matching Polytope

The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that $${\mathbf y}^* = \arg\...