Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
3
votes
1answer
106 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
117 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 ...
-1
votes
0answers
14 views
Spidergon Networks-on-Chips
What do you guys think about Spidergon NoC ?
Why mod 4 ?
And do you guys understand how the shortest path routing algorithm depends on the value of RelAd ?
The original paper : Spidergon: a novel on-...
3
votes
0answers
68 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
121 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
80 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
110 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
39 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
83 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
76 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
119 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
108 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
68 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
85 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
184 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:
...
2
votes
0answers
145 views
A variant of the Maximum Weight Clique problem
I am trying to solve a problem that I could reduce to the following:
Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
3
votes
2answers
167 views
Finding a set which dominates the Minimum Dominating Set
Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.
The dominating set problem is NP-hard, but I am considering ...
4
votes
2answers
137 views
Max cut problem between two connected subgraphs
Let $G$ be a connected graph.
Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
-2
votes
1answer
101 views
Finding Cheapest n-Path [closed]
Given a weighted directed acyclic graph, how can I find the cheapest path from an Origin Vertex to a Destination Vertex which ...
2
votes
0answers
39 views
Min cut problem on unbalanced partitions for planar graphs with unit capacity edges
The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
5
votes
1answer
95 views
Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem?
The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability ...
4
votes
1answer
177 views
Fast algorithm to find a maximum connected subgraph of k vertices
Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
3
votes
1answer
108 views
Finding a “lowest” path in a graph
I have an undirected graph $G = (E,V)$, $|V|=n$,
where each node $v_i$ has a natural number weight.
Think of these weights as heights $h_i$.
Given two nodes $s$ and $t$, I'd like to find a lowest ...
4
votes
2answers
142 views
Check if graph stays connected after edge swap
Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
3
votes
1answer
199 views
What exactly is Lawler's modification to Yen's algorithm and how does it work?
I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as ...
4
votes
1answer
379 views
Minimum Union-Sum Cost Path
I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
1
vote
0answers
53 views
k-center 2.0: A stronger k-center condition
Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.
Note that ...
3
votes
1answer
47 views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$.
I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
6
votes
1answer
240 views
Computing topological sort while keeping edges “short”
Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.
Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
0
votes
1answer
51 views
What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?
I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of
Counting the number of distinct s-t cuts in a oriented graph
It says ...
6
votes
1answer
134 views
Partition edges into edge disjoint walks
Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$.
A set of $k$ walks is called a $(S,T)$-walk partition if
the walks form a ...
3
votes
0answers
116 views
Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]
We got an argument that 3-coloring bounded degree graphs is subexponential
with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.
The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-...
5
votes
1answer
153 views
“Smallest” path that visits a given set of vertices
I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:
Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ ...
1
vote
1answer
86 views
What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?
I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.
8
votes
2answers
400 views
Counterexample to max-flow algorithms with irrational weights?
It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the ...
13
votes
1answer
340 views
What are the obstructions to extending $L=SL$ to $L=NL$?
Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
1
vote
2answers
191 views
Is perfect matching for bipartite graph with no cycles unique?
Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.
My question is if the balanced bipartite graph is also ...
-1
votes
1answer
301 views
Closeness Centrality for Weighted Graphs
In order to determine the Closeness Centrality for a vertex u in a graph, you compute the shortest path between u and all other vertices in the graph. The centrality is then given by:
$C(u) = \frac{1}...
6
votes
0answers
72 views
Complexity of bounded degree full contraction
This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows:
Instance: A graph $G$ and two integers $d$ and $k$.
Question: Is there a ...
5
votes
0answers
167 views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
3
votes
0answers
101 views
Graph-related applications of the fast Fourier transform (and other algebraic algorithms)
The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).
However, while the fast Fourier transform algorithm implies several other near-...
16
votes
1answer
398 views
What is the complexity of this graph problem?
Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that
for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and
the size of $A$ is ...
2
votes
1answer
114 views
What is the name of this algorithm on direct acyclic graph?
I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.
In ...
1
vote
0answers
98 views
Generalized path cover problem in DAG
Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
-1
votes
1answer
37 views
Maximize graph with k cut edge operations
I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 ...
5
votes
2answers
224 views
Efficient way to generate random planar cubic bipartite graphs
3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
5
votes
0answers
67 views
Series-parallel extension of a partial order respecting a given total order
Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.
An $O(n^3)$ ...
1
vote
0answers
26 views
Complexity of recognizing generalized graph join
A join of two graphs is the union of both graphs with additional edges such that every vertex of the first graph is connected to every vertex of the second graph. There is a generalization of this, ...
