Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

0
votes
0answers
5 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
42 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
44 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
52 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}$ ...
1
vote
1answer
86 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
18 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 ...
15
votes
2answers
659 views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
0
votes
1answer
52 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 ...
3
votes
2answers
146 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 ...
2
votes
1answer
112 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 ...
0
votes
1answer
77 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 ...
0
votes
0answers
28 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
73 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 ...
6
votes
0answers
159 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. ...
17
votes
1answer
458 views

Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
24
votes
5answers
5k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
5
votes
1answer
144 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
101 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 ...
9
votes
2answers
581 views

Computing a transitive completion / path existence oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
1
vote
1answer
59 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
129 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
3k 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
130 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
660 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) ...
3
votes
0answers
92 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 ...
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
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....
4
votes
1answer
418 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
123 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
114 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
102 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
78 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
127 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
963 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
112 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
92 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
70 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
775 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
146 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
188 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
191 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
596 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
87 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.