Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
1,082 questions
2
votes
0
answers
53
views
Packing induced $P_3$s and their complements
I'm interested in vertex-disjoint packing of induced $P_3$s (paths on three vertices) and their complements. Is this problem NP-hard?
Observation: A graph is $\{P_3, \overline{P_3}\}$-free if and only ...
- 2,619
0
votes
0
answers
64
views
Break finding on a graph
Given a graph with $n$ nodes where some of the edges are defective and two nodes $u,v$ of the graph which are not connected by a path of non defective edges, I am allowed to query any two nodes $a,b$ ...
- 358
-1
votes
1
answer
51
views
Are there any approximation algorithms for two terminal reliabiity in undirected graphs?
Let $G = (V, E)$ be a graph. Each edge $e = (u, v) $ is associated with a failure probability $0 \leq q_e < 1$.
Given two vertices $s, t \in V$, the $s$−$t$ reliability problem asks the ...
- 358
1
vote
1
answer
125
views
Problem on a Directed Graph subcase of load time scheduling
I have the following graph optimization problem. In a directed graph G, each node $v$
is assigned a number $n(v)$ which is initially 0. At any time, I can make a move to assign the number $ max \{ n(...
- 358
2
votes
1
answer
1k
views
In what sense is this algorithm better than Dijkstra?
A recent publication (Duan, Ran, et al. "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025) ...
- 83
1
vote
1
answer
128
views
Domination between sets of nodes in a union of tournaments
Let $G$ be a directed graph obtained from the union of two tournaments $T_1$ and $T_2$ on the same vertex set, plus a loop arc on each vertex. We can assume that the tournaments $T_1$ and $T_2$ are ...
- 442
2
votes
1
answer
99
views
Is there an online tool to compute the treewidth of a given graph?
I have an explicit graph (not too big) and I want to compute its treewidth. Is there a Web tool where I can provide the graph (given, e.g., by its explicit list of edges) and obtain its treewidth?
- 10.9k
2
votes
0
answers
74
views
How updated is the ISGCI database?
According to the Information System on Graph Classes and their Inclusions (ISGCI) database, the complexity class of the MAXCUT problem for the following graph families (and) is still unknown. How ...
- 691
5
votes
0
answers
123
views
Listing spanning trees of a complete graph with constant delay
We are looking for any known algorithms/lower bounds related the the following problem:
Enumerate all spanning trees of a complete graph by edits with constant delay (linear time preprocessing allowed)...
- 151
0
votes
1
answer
403
views
I have written a preprint about a novel algorithm to find MST, I think it can be a replacement for Kruskal's algorithm; Can any anyone review it?
I am a recent CS Grad, and I wrote a preprint about a algorithm for MST, with time complexity O(E+VlogV) and Ω(E) in the worst and base cases, respectively; given sorted edges. I feel like it is a ...
6
votes
1
answer
166
views
Laying out pages for a “choose your own adventure” book?
I’m writing a “choose your own adventure” style book. Each page contains some text followed by a series of options, each of which instructs the reader to turn to a different page.
I can model the ...
- 2,412
7
votes
1
answer
192
views
Reachability with ordered exclusive pairs
This question is about the reachability problem finding a path from a vertex
$s$ to a vertex $t$ in a directed graph $G = (V, E)$ subject to a specific kind
of exclusive pairs requirement. Formally, ...
- 73
0
votes
1
answer
56
views
An algorithm for finding the optimal process order for finishing a set of processes with prerrequisites and a maximum amount of processes per stage
The problem is to find the minimum number of stages in which we can finish a set of processes, where we have a maximum number of processes we can do per stage, and there are prerequisites for the ...
- 1
-2
votes
1
answer
178
views
Status of the Graph-Isomorphism problem when $n\le k$ for some $k$
Consider a poly-time algorithm that attempts to solve the GI problem on general graphs. However, the algorithm can only guarantee that it correctly decides the problem for a specific range of values ...
- 273
2
votes
1
answer
375
views
Complexity of counting the number of cycles through a particular edge
It is known that counting cycles in a graph is a hard problem (#P-hard). However, what do we know about the following problem:
Given a simple, undirected graph $G$ and an edge $e$ of $G$ as input, ...
