Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

3
votes
1answer
99 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 ...
2
votes
2answers
2k views

What are the algorithms and the data structures for GUIs and input management?

I'm studying how, given: an input from the user ( like a click of the mouse or the input from a key ) a well defined data structure that represent the graphical layout inside a window ( a tree/graph ...
0
votes
1answer
116 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 ...
11
votes
2answers
653 views

Graph classes for which the diameter can be computed in linear time

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
-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 ...
-2
votes
0answers
21 views

Finding all spanning trees of a directed graph

I wonder if there is a well-known algorithm (or optimized implementation) for this.
7
votes
2answers
4k views

How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead. Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
1
vote
1answer
78 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....
4
votes
1answer
377 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 ...
44
votes
4answers
12k views

Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
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 ...
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 ...
1
vote
2answers
8k views

Algorithm for Max Network Flow with lower bounds and its complexity

I have built a max network flow graph that carries certain amount of people from a source to a destination. Now, I'd like to attach a lower bound $l_(e_)$ constraint to each edge $e$. But I don't know ...
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 ...
3
votes
1answer
844 views

Minimal Cost of Eulerian Path

Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
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
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 ...
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
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 ...
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 ...
21
votes
5answers
2k views

Program for computing Tree decomposition of a graph

Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
19
votes
2answers
773 views

Axioms for Shortest Paths

Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
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_{...
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: ...
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 ...
11
votes
0answers
234 views

Inapproximability of multiterminal cut

In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
4
votes
0answers
529 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
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.
4
votes
2answers
135 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$...
8
votes
1answer
164 views

Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this ...
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 ...
14
votes
2answers
442 views

The existence of planar distance preserver?

Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property $$d_H(u,v) = d_G(u,v)$$ for all nodes ...
9
votes
1answer
256 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
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 ...
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 ...
37
votes
4answers
1k views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational 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 ...
2
votes
3answers
5k views

shortest path & max flow

I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book. We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ ...
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 ...
6
votes
2answers
671 views

Edge and vertex fault tolerance in graphs

Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What ...
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 ...