Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
74 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 $...
Samdney's user avatar
-1 votes
1 answer
71 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 ...
Vetrivel's user avatar
0 votes
1 answer
67 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 ...
user1454590's user avatar
3 votes
0 answers
68 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 ...
a3nm's user avatar
  • 8,896
0 votes
1 answer
65 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 ...
John's user avatar
  • 173
0 votes
0 answers
64 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 ...
Balchandar Reddy's user avatar
4 votes
1 answer
63 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 ...
Timothy Chow's user avatar
  • 7,465
1 vote
1 answer
103 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 ...
user69908's user avatar
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 ...
user135520's user avatar
3 votes
1 answer
98 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 ...
Balchandar Reddy's user avatar
1 vote
1 answer
46 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 ...
Naysh's user avatar
  • 576
4 votes
1 answer
85 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 ...
Command Master's user avatar
0 votes
1 answer
67 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 ...
Adam Jamil's user avatar
2 votes
0 answers
99 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$ ...
sally's user avatar
  • 21
0 votes
1 answer
101 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 ...
user69635's user avatar
0 votes
0 answers
39 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 ...
Dowdow's user avatar
  • 9
3 votes
1 answer
99 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 "...
Marco Pegoraro's user avatar
0 votes
0 answers
87 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 ...
iheap's user avatar
  • 195
4 votes
0 answers
84 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 ...
jfriemel's user avatar
3 votes
1 answer
195 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 ...
Franklin Pezzuti Dyer's user avatar
3 votes
0 answers
67 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 ...
Z.L's user avatar
  • 31
3 votes
0 answers
109 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 ...
walydna's user avatar
  • 63
1 vote
0 answers
46 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 ...
sripurva's user avatar
1 vote
1 answer
45 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.) ...
Inspired_Blue's user avatar
2 votes
1 answer
236 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 ...
Balchandar Reddy's user avatar
3 votes
0 answers
76 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 ...
Germ's user avatar
  • 131
1 vote
0 answers
42 views

What are the fastest known parameterized algorithms for Grid Tiling?

Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
Naysh's user avatar
  • 576
1 vote
1 answer
221 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: ...
Sebastian Szczepański's user avatar
1 vote
0 answers
66 views

Finding a Hamiltonian cycle in a graph if we are guaranteed that there are not many of them in the graph

Problem: Given an undirected simple graph $G=(V,E)$ on $n$ vertices, such that there are not more than $c^n$ ($c<2$) Hamiltonian cycles in $G$, find a Hamiltonian Cycle in $G$ if there exists one. ...
jamal_asif's user avatar
2 votes
0 answers
66 views

Confusion with the definition of Online Set Cover

I am confused on a technicality on how Online Set Cover is defined. One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
Karagounis Z's user avatar
1 vote
0 answers
52 views

Approximation algorithm for non-bipartite Euclidean matching

What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are ...
Sandip's user avatar
  • 11
3 votes
1 answer
201 views

Cover a graph with complete graphs

I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
walydna's user avatar
  • 63
1 vote
0 answers
37 views

Minimum vertex-separators under edge addition

I am trying to prove the following claim. Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$. Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
BBK's user avatar
  • 95
2 votes
0 answers
100 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?
geeko's user avatar
  • 131
0 votes
1 answer
66 views

Resources for first-order and second-order monadic logics with a model-checking objective

What are some good books and surveys for learning about first-order logic and monadic second-order logic? I'm a graduate student in computer science with a focus on algorithms. For model-checking on ...
fva's user avatar
  • 45
0 votes
0 answers
45 views

Maximum independent set in "subgraph-claw-free" graphs

A $d$-claw in a graph is a set of $d+1$ vertices, one of which (the "center") is connected to the other $d$, but the other $d$ are not connected to each other. A graph is called $d$-claw ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
77 views

increasing minimum graph degree by adding edges

My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$. Is there a polynomial-time ...
jpcasti's user avatar
  • 33
0 votes
0 answers
65 views

Maintaining a $K_{3,3}$-minor-free graph

Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free. Let $a,b\in V(G)$ be non-adjacent vertices. Under what conditions is the graph that results by adding the edge $(a,...
BBK's user avatar
  • 95
0 votes
1 answer
74 views

Spectral sparsification of graphs with negative edge weights

I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question. It is ...
K V's user avatar
  • 1
3 votes
1 answer
152 views

Hardness of Maximum Independent Set in 3-Colorable Graphs

Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors. Question: In such graphs, are there known results for the hardness of finding a ...
John's user avatar
  • 173
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 ...
a3nm's user avatar
  • 8,896
3 votes
1 answer
192 views

Solving linear programs with special structure

We have an application and at some point we need to solve a linear programming problem that looks like this: $$ \min\ w_{1,2} + w_{3,4} + w_{5,6}\\ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\ x_1 - ...
Maltus's user avatar
  • 73
1 vote
0 answers
103 views

On the borderline between natural and artificial problems

While there is no formal definition of what constitutes a natural algorithmic problem, in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
Andras Farago's user avatar
1 vote
0 answers
26 views

Can input-output matrices optimize bidirectional search?

Given a bidirectional search on a weigthed digraph, could a modified input-output matrix guess what nodes are more likely to belong to the shortest path and the search be done through these nodes ...
Gabriel Andrade's user avatar
0 votes
1 answer
133 views

2xn grid graphs from ring graphs via local complementations

(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
Dotman's user avatar
  • 109
4 votes
1 answer
185 views

Finding a "typical" path

Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible? Formally, for ...
Andras Farago's user avatar
-1 votes
1 answer
85 views

Solution for a bipartite demand and supply graph

Given a set of distinct nodes ($A \cup B$) one set represents nodes with a supply ($supply(a), a \in A$) and the other represents nodes with a demand ($supply(b), b \in B$). In a bipartite graph I am ...
Bernd Strehl's user avatar
2 votes
0 answers
105 views

Small set expansion and expanders

Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets: $$ h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ , $$ with $$\phi(...
loplo's user avatar
  • 41
4 votes
0 answers
96 views

Time Complexity of Pairwise Graph Connectedness

The Setup Consider the following algorithmic problem which, for now, I will call $\mathsf{2GraphConnector}$. Input: A natural number $|V|$, and a finite collection $\mathscr{E} = \left\{E_1, E_2, \...
k-variant's user avatar
3 votes
1 answer
135 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 ...
kostrykin's user avatar
  • 139

1
2 3 4 5
21