Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
-2
votes
1answer
212 views

questions on implications Babais quasi P time graph isomorphism result

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs. based on the proof, does this mean now that if Johnson ...
2
votes
1answer
176 views

Efficient enumeration of the reachable leaves of nodes in a polytree

A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart. Given a polytree $T$ and a node $...
5
votes
0answers
130 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
-2
votes
1answer
229 views

Bounded 0/1-knapsack with dependency constraints without limit

Consider a set of items, weighted with real numbers / costs. You are supposed to select a subset maximizing the sum of the weights of the selected items. But the following contraints must be observed: ...
2
votes
1answer
256 views

Partition refinement in transition state systems (bisimulation contraction)

I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ...
3
votes
3answers
168 views

Approaches for Theoretical Analysis of Estimates of Probability Distributions

Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
8
votes
2answers
213 views

Nonstandard dual parametrization of graph problems

One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when ...
-1
votes
1answer
891 views

Reachability on DAG (best-known algorithm)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, ...
0
votes
1answer
94 views

Number of bounded minimum vertex covers

Minimum Vertex Cover problem Input: $G=(V,E)$ and Parameter $k$ Output: Decide whether there exists minimum vertex cover of size at most $k$. Question:- Can we bound the number of minimum vertex ...
3
votes
1answer
112 views

Shortest cycle separator for biconnected planar graphs

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is ...
2
votes
1answer
407 views

Max weight k-clique

Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however ...
3
votes
1answer
141 views

Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known. The ...
2
votes
1answer
265 views

Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in ...
9
votes
0answers
314 views

Triangle arrangement problem

Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
4
votes
0answers
140 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete?...
1
vote
1answer
147 views

Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $...
1
vote
1answer
934 views

Longest path from every vertex in a tournament

I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path ...
1
vote
0answers
1k views

Fastest Algorithm for the Minimum Edge Covering Problem

Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints: G' must include all the ...
3
votes
1answer
209 views

Finding a graph that minimizes the number of nodes for a given number of paths

There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting ...
1
vote
0answers
98 views

Detecting bridges in Hypergraph S-t Reachability

Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
8
votes
2answers
728 views

Dichotomy of the spectra of directed graphs

Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known: It is known that a directed graph $G = (V,E)$ has an adjacency ...
1
vote
0answers
94 views

Concentration Bounds for functions of matrices

This is a question about properties of large directed graphs which are preserved when we randomly sample edges. Imagine I have an infinite sequence of positively weighted directed graphs. The ...
2
votes
1answer
267 views

Are there any results on the following “generalized matching” problems?

Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic ...
8
votes
2answers
200 views

Something-Treewidth Property

Let $s$ be a graph parameter (ex. diameter, domination number, etc) A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph $G\in \mathcal{...
10
votes
3answers
777 views

Shortest distance problem with length as functions of time

Motivation The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two ...
4
votes
2answers
459 views

Does the problem “partition a vertex-weighted graph into $k$ balanced connected parts” have a standard name?

Consider the following problem: Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
4
votes
1answer
157 views

Bidirectional A*: is an update of the distance estimation feasible while searching?

The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal. The ...
0
votes
1answer
123 views

The number of edges in the ith shortest path in a directed graph

$G$ - directed graph, $n$ - count of nodes According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges. Anybody can explain how this estimate is ...
-5
votes
2answers
2k views

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
6
votes
2answers
401 views

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
1
vote
1answer
339 views

Triangular Mesh Reordering - Huddling Triangles

I am given a 3D model represented by its outside surface as a triangular mesh (hollow inside). The model is mostly 2-manifold, so that each triangle edge is shared by exactly 2 triangles. This, ...
2
votes
1answer
153 views

Maximum cardinality subgraphs meeting a Jaccard overlap threshold

Consider two undirected connected graphs $G_0$ and $G_1$. The graphs are subgraphs of a given connected graph $G$ and share at least one node. I want to find two subgraphs $G_0'\subseteq G_0$ and $...
1
vote
2answers
220 views

Reduction from independent set in hypergraphs to independent set in graphs

Let me introduce my notations. IS-H : Input : an hypergraph $G=(V,H)$, an integer $k$ Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
1
vote
0answers
104 views

algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
0
votes
1answer
236 views

Cluster Edge Deletion on 2-trees

Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced ...
-2
votes
1answer
527 views

Finding All Cliques of an Undirected Graph

How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)
0
votes
1answer
176 views

Efficient update of reachable set of a node in a digraph

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , ...
2
votes
0answers
488 views

Path finding on graph with state dependent edge costs

I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i....
0
votes
2answers
332 views

Efficient algorithm for testing planarity of the union of two planar graphs

Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs. Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar? That is, an algorithm more efficient than ...
2
votes
1answer
343 views

Graph planarity testing via adjacency matrix

I have looked at several efficient graph planarity algorithms which rely on computing and traversing DFS trees (that add one vertex/edge/path at a time). I am looking for graph planarity algorithms ...
7
votes
1answer
362 views

Complexity of “destroying” the graph's minimum spanning tree weight

Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$. Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
6
votes
0answers
788 views

Minimum vertex k-cut

Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at ...
2
votes
1answer
75 views

Constant Width Max Sum Product Multi-objective Shortest path problem

This question is a follow-up on the question I asked three days ago here. For convenience I restate it here. I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...
4
votes
1answer
161 views

Max Sum Product Multi-objective Shortest path problem

Is anything known about the following problem: I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1. A path is first assigned a vector, ...
16
votes
0answers
300 views

Complexity of the homomorphism problem parameterized by treewidth

The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $...
6
votes
1answer
183 views

On bandwidth of graphs

I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance. I could only find research related to computing the bandwidth, ...
4
votes
0answers
185 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
3
votes
1answer
336 views

What is the best known FPT result for 3-hitting set?

My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for ...
7
votes
1answer
263 views

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3). ...
2
votes
0answers
84 views

Max common sub forest on $k$ graphs

Not sure how to phrase this really, but here goes. Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$. The problem is to find ...