# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
44 views

### Mechanism of Howard's algorithm [closed]

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
137 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.
82 views

### Expected number of node visits during random walk

Say we have a graph $G = (V,E)$ and all we know about the graph is the degree $deg(n)$ of each node $n$, $|V|$, and $|E|$. Say we begin a random walk of length $l$ starting at a random node. What is ...
267 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 ...
130 views

94 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 ...
95 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 ...
348 views

42 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 ...
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 ...
231 views

142 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 ...
53 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, ...
189 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$ ...
26 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 ...
521 views

### Algorithms for graph generation given parameters

I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am ...
1k views

### Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is ...
335 views

### Check if graph stays connected after edge swap

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
472 views

### Linear-time algorithm to test if clique number equals degeneracy bound?

Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique. A well-known bound on the clique number is $\omega\le d+1$, which is ...
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....
2k views

### Count $k$-hop neighborhood for every vertex

For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
6k views

### How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead. Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
836 views

### Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

What is the fastest known undirected graph isomorphism algorithm?
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 ...
146 views

### Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...