Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
3 votes
1 answer
368 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
2 answers
883 views

Max flow: either saturate an edge or avoids

Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
4 votes
1 answer
364 views

How do you achieve linear time complexity of greedy graph coloring?

In most resources I could find, greedy algorithm is described as follows: for every vertex $v$, assign the minimal color not used by its neighbors. The above could be implemented as: ...
3 votes
0 answers
46 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 ...
0 votes
1 answer
26 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 ...
2 votes
1 answer
30 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$, ...
1 vote
0 answers
65 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, ...
0 votes
1 answer
55 views

Question about claw-free graphs

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
12 votes
2 answers
695 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 ...
3 votes
1 answer
75 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....
1 vote
0 answers
32 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 ...
3 votes
2 answers
166 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 ...
1 vote
1 answer
141 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
2 votes
0 answers
37 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 ...
2 votes
1 answer
197 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
2 votes
1 answer
99 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 ...
0 votes
0 answers
45 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 ...
5 votes
1 answer
490 views

Can Lexicographic BFS be implemented in logspace?

Input: Given graph $G=(V,E)$ with vertices labeled in some order Output: Change the labeling of vertices such that the labeling starts $v_1$ as $u_1$. Next, label the neighbors of $v_1$ as $u_2,u_3,...
-1 votes
1 answer
83 views

Representation of binary strings by graphs and hypergraphs

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$. Question: Which further ways of representing binary strings of length $...
1 vote
1 answer
629 views

Generate TSP instances with known optimal

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? The idea is to be able to generating arbitrary large instances with known optimal value,...
-1 votes
1 answer
82 views

Generating grammar from a string

Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string? Problem statement - I'm trying to build a code base scanner, and I'd like to ...
0 votes
1 answer
81 views

A variation of the longest path problem

What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ? EDIT: X would be ...
3 votes
0 answers
84 views

FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge ...
0 votes
1 answer
68 views

Is this edge-partitioning NP-Hard?

Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$). Problem: Partition $E$ to $q = \frac{m}{3}$ sets $S_1,S_2,\ldots, S_q \subseteq E$ sets ...
0 votes
0 answers
68 views

Enumerating all set covers with sets of size at most two

I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in $O^*(1.2353^{|U|+|S|})$ time that branches on all the sets of size at least three. As the branching ...
4 votes
1 answer
71 views

Complexity of maximum k-edge-colorable subgraph of a bipartite graph

Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
0 votes
1 answer
129 views

Complexity and Algorithm for specific Vertex Separator Problem

Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to ...
3 votes
1 answer
103 views

Running time analysis of problems with a variable in problem definition

I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $[1,j]$-domination problem. Given a graph $G = (V, E)$, $n = |V|$, the problem ...
4 votes
1 answer
89 views

Independent set queries with preprocessing

Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
0 votes
0 answers
25 views

Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent

I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative ...
12 votes
1 answer
2k views

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
1 vote
1 answer
58 views

What is known about the complexity of Network Diversion?

In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
0 votes
1 answer
205 views

Transitive reduction not provably minimal [closed]

Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ...
0 votes
1 answer
79 views

What's the exact complexity of a DFS if we revisit nodes?

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
3 votes
1 answer
142 views

Approximative counting of matchings in a graph

The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
2 votes
0 answers
101 views

Two disjoint paths with minimum product of weights -NP-completeness

I want to know whether the following problem is NP-complete; Given an undirected graph $G=(V,E)$ with weights on each edge $e\in E$, and two vertices $s,t\in V$, find two disjoint paths $P_1, P_2$ ...
3 votes
1 answer
112 views

Maximum cardinality matching on DAGs

A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "...
0 votes
0 answers
51 views

Why are impossibility results harder for uniform sparsest cut than non-uniform?

My question is this: why is it the case that the uniform cost version of the Sparsest Cut problem has eluded hardness of approximation results whereas the non-uniform version has not; my intuition is ...
8 votes
0 answers
171 views

Can one find good distance-2-separators in planar graphs?

It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph. However, it ...
0 votes
0 answers
93 views

Consequences of early-exiting BFS after reaching the target node in Dinic's algorithm

In a typical exposition (or implementation), Dinic's algorithm executes a full BFS traversal of the residual graph starting from the source node in each phase. If the target node is unreachable, the ...
4 votes
0 answers
94 views

Linear-time maze exploration for finite automaton with pebbles?

Blum and Kozen have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may ...
4 votes
1 answer
292 views

Implementations of Undirected Disjoint Paths

I'm looking into the Undirected Vertex Disjoint Paths problem: Given a list of tuples of vertices (s_i, t_i) Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects ...
3 votes
1 answer
252 views

Priority queue implementation with both find-min and delete-min $o(\log n)$

Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: Does anyone know of an implementation in which the ...
3 votes
0 answers
68 views

Property testing algorithm for isomorphism to a balanced 3-sided complete graph

I am looking for testing algorithm in the dense graph model, that checks for a graph with $3n$ vertices whether it's isomorphic to a balanced 3-sided complete graph with $n$ vertices in each set. The ...
3 votes
0 answers
117 views

Cover all triangles of a graph with n subgraphs as small as possible

What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
26 votes
3 answers
1k views

Optimization problems with minimax characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
1 vote
0 answers
47 views

Max Flow Routing

Let G = (V,E,S,I,T) be a directed flow network with nodes V, edges E with unit capacity, source nodes S $\subseteq$ V, intermediate nodes I $\subseteq$ V, and target nodes T $\subseteq$ V. The problem ...
1 vote
1 answer
60 views

Efficient algorithm/ implementation to compute Transitive Closure of a Rule with respect to a Relationship

(Recalling some) Definitions: Fix a finite collection of finite sets: $A_1,\ldots,A_k$. Then relationship $R\subseteq A_1 \times A_2 \times \ldots\times A_k$. (Remark: $A_i$'s need not be distinct.) ...
2 votes
1 answer
247 views

6-regular graph without small 3-regular subgraph

My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 6-regular graph that does not have small 3-regular subgraphs. For example, I ...
3 votes
0 answers
81 views

Is there an algorithm for reducing the average row width of a sparse matrix?

Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be: $$w_i \equiv r(A_i) - l(A_i),$$ where $r(A_i)$ is the index of the rightmost nonzero element ...

1
2 3 4 5
21