Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
845
questions
-5
votes
0answers
46 views
Randomized algorithm for clique that proves P = NP [closed]
Suppose there is a polynomial-time randomized algorithm which for graph $G$ and natural number $k$ with probability not less than $2/3$ correctly answers the question whether or not there is a clique ...
1
vote
1answer
74 views
Finding simple fixed length paths in directed graphs
Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?
0
votes
1answer
66 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
9
votes
2answers
263 views
How long does it take to find a short cycle in a random graph?
Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
10
votes
2answers
171 views
“Relatives” of the shortest path problem
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
3
votes
0answers
106 views
Enumerating Minimal (a,b) vertex separators in a DAG
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.
$S$ is a ...
2
votes
1answer
105 views
Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free
What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs ...
3
votes
1answer
99 views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.
There is also a parameterized algorithm for ...
1
vote
0answers
77 views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
8
votes
1answer
220 views
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
2
votes
0answers
67 views
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
I have encountered an interesting problem that I couldn't find any references to solve:
Determine the smallest subset of nodes that
need to be removed from an undirected graph to make it a tree.
...
0
votes
0answers
43 views
Matching of two weighted graphs allowing one-to-many mapping
I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
1
vote
0answers
50 views
Directed Acyclic Graph partition into minimum subgraphs with a constraint
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
2
votes
0answers
73 views
Common techniques for the acyclic orientation problem under some special constraint?
An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
5
votes
0answers
243 views
Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?
Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
10
votes
1answer
210 views
Efficient graph isomorphism for similar graph queries
Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one ...
0
votes
0answers
19 views
Connectivity with ordered adjacency list
In the adjacency list model, a graph is described through lists that contain the neighbors of any node $i \in [n]$. A query is of the form "What is the $k$-th neighbor of node $i$?". BFS allows to ...
2
votes
1answer
68 views
Computing the existence of a path in a code execution graph
I have a need for an algorithm which I can express as a reachability problem in a graph.
Note that I'd appreciate any advices with respect to better wording this question. Also please tell me if this ...
0
votes
0answers
66 views
Unknown gaps in computation models
I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2.
where T1 is smaller then T2 and it is unknown if there are problems where their ...
0
votes
1answer
80 views
finding maximum weight subgraph
My graph is as follows:
I need to find a maximum weight subgraph.
The problem is as follows:
There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...
3
votes
0answers
53 views
Algorithms for Maximum weight connected subgraph in planar graphs
I wonder what is known about the two following maximisation problems.
Maximum weight connected subgraph :
Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$
Output :...
-1
votes
1answer
48 views
Min Cut with Vertices
I have an undirected graph G with a set of vertices and edges. Each vertex has a weight w. Let's assume we have all vertices connected with some paths. I'm looking ...
1
vote
0answers
56 views
Graph automorphism with prescribed values
Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ ...
2
votes
1answer
163 views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
0
votes
0answers
19 views
The set of weight functions for which the assignment problem has non-trivial solutions
The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs):
$$
V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij},
$$
where $\cal P$ is a ...
0
votes
1answer
62 views
Finding a Hamiltonian cycle from perfect matching of a bipartite graph
A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ...
4
votes
3answers
282 views
Is counting simple cycles in $P$ for graphs of bounded tree width?
Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ...
0
votes
0answers
29 views
Alternating Delivery Problem
What is known about the complexity of the following problem:
Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...
1
vote
0answers
80 views
Minimum cut with nonlinear objective function
Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum.
Let us generalize it the following way: let $f$ be a ...
0
votes
1answer
82 views
Densest k subgraph problem for outerplanar graphs?
The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$.
Does anyone know if there exists a polynomial-time ...
6
votes
0answers
182 views
Largest “non-disturbing” subset in a graph
The definition:
The subset of vertices in a graph is called "non-disturbing" if any two vertices from this subset could be connected by a path not passing through other vertices of this subset.
...
5
votes
1answer
153 views
Minimum cost cut with discount - what is the complexity?
Consider an undirected graph $G=(V,E)$ with non-negative edge costs. Given an integer $k$ with $0\leq k\leq |E|$, let us call an edge set $C\subseteq E$ a $k$-discounted cut, if the following hold:
$...
2
votes
0answers
121 views
Shortest s-t path when is allowed to ignore k weights
Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
1
vote
1answer
63 views
Complexity status of the Edge Deletion problem to bounded degree graphs
I'm interested in the complexity status of the following problem.
Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$.
Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...
3
votes
1answer
145 views
How is SDP an extension of spectral algorithms?
In one of his lectures, Uri Feige described semidefinite programming (SDP) as
... an algorithmic technique that extends both linear programming and spectral algorithms.
I know the basic ...
0
votes
1answer
145 views
Data Strcuture to represent dependencies amongst modules
Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
3
votes
0answers
156 views
Generating a random connected bipartite graph
A (n, m, k)-bipartite graph is a bipartite graphs with:
independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges
We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
1
vote
0answers
124 views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
1
vote
1answer
82 views
Algorithm for K-best NON perfect bipartite matchings
I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf
It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
6
votes
0answers
121 views
Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications
Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
1
vote
0answers
40 views
Optimally fair stable matching
There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively.
In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...
-1
votes
1answer
119 views
When is extra vertex required in arbitrage detection using Bellman Ford?
I am studying applications of shortest path, in particular arbitrage.
Specifically, I was reading these two resources:
https://stackoverflow.com/questions/2282427/interesting-problem-currency-...
1
vote
1answer
80 views
Pulling a graph across a partition
I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
2
votes
0answers
132 views
Crime prevention using graph theory and machine learning
I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
1
vote
1answer
44 views
Problem property name where an optimal solution in a graph can be used as a solution in any subgraph
Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
5
votes
1answer
117 views
Counting/Enumerating Minimal Edge Covers
A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.
Questions
Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
1
vote
1answer
74 views
Color shifting in a bipartite graph
Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
2
votes
0answers
101 views
Counting the maximum number of paths of length $n$ that differ in at least $k$ edges
What is known about the complexity of solving (or approximately solving) the following problem?
INPUT: Graph $G=(V,E)$ and constants $L$ and $K$.
OUTPUT: The maximum size of any set $S$ of simple ...
1
vote
0answers
51 views
Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity
I am wondering if this is a topic that has had research done...
If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
8
votes
1answer
190 views
Could chromatic number be easy to calculate when colouring is hard for some graph class?
Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring
Is there any infinite set of graphs $C$ such as:
...
