# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

1,045 questions
Filter by
Sorted by
Tagged with
17 views

### Escaping the cycle: Route planning in graphs with conditional logic

Given a directed graph $G(V, E)$, I want to find a route, $R \in E^*$ from $S$ to $T$ for $S,T \in V$. If $G$ includes a cycle, how can I find a route that includes $n$ iterations of the cycle before ...
133 views

### Orientations of an undirected graph

I would like to ask about an approach to find the min. number of edge orientations to ensure that a specific subset of nodes (between which demand exists) in a weighted undirected graph is eventually ...
1 vote
116 views

### Graph canonization vs. NP

Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why? GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a ...
• 267
94 views

### Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?

I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
• 639
1 vote
37 views

### On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
• 11
35 views

### Enhancing a bipartite perfect matching solution with 1-to-2 matchings

We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
51 views

### Cuthill - Mckee Guarantees?

I'm interested in the following problem: given $M$, a $p \times p$ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a ...
• 131
32 views

### How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

I am working on a problem where I have $n$ workers, each with a cache that already contains a specific set of objects. Additionally, I receive $n \times m$ sets of objects. My task is to assign ...
• 33
38 views

### Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

Similar with Weighted matching algorithm for minimizing max weight. Consider the following matching problem: Input: a complete weighted bipartite graph with $n+(k*n)$ vertices, given by $n$, $k*n$, ...
• 33
1 vote
77 views

• 103
707 views

### Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
1 vote
37 views

### How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
• 11
42 views

### Hardness of Coloring based on a Black-Box Hardness of Independent Set

It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent ...
• 412
171 views

### Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes. Does this have a constant approximation? ($p,k$ and the graph are all part of the ...
• 228
80 views

### What is the fastest algorithm for computing exact network reliability?

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
• 686
54 views

### Minimum spanning tree with only edge ordering

It seems like, given an undirected graph $G = (V, E)$ with distinct edge weights, one only needs an ordering on $E$ to run Kruskal's algorithm. This tells me that the (distinct) minimum spanning tree ...
111 views

### Maximum cardinality disjoint cycle cover in undirected graphs

I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
• 828
96 views

• 103
118 views

### Does GHC use graph reduction?

I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
• 131