Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
4
votes
0answers
138 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
145 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
928 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
207 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
97 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
693 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
263 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
198 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
760 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
449 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
156 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
397 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
317 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
152 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
217 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
235 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
506 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
170 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
482 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
330 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
334 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
356 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
770 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
74 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
158 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
296 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
180 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
323 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
254 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 ...
4
votes
1answer
430 views

The maximum number of induced cycles in a simple directed graph

Is the maximum number of induced circuits in a simple directed graph known? I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly $3^{n/3} + \frac{...
7
votes
1answer
142 views

Label-disjoint paths in directed graphs

Checking if there are two edge-disjoint paths from $s$ to $t$ in a given undirected graph $G$ is in P via a standard solution based on maxflow. I am interested in the complexity of the following ...
3
votes
0answers
90 views

Maximum weight triangles in dense graphs

There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs. Several of these ...
1
vote
1answer
171 views

Max network flow with arbitrary source / sink

I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices s and t, how different is the problem to calculate the max flow between the vertices s' and t, or ...
7
votes
1answer
305 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
2
votes
1answer
673 views

Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or non-...
6
votes
2answers
228 views

Parametrized complexity of the 2-Long Paths Problem

Consider the following problem: Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$...
0
votes
0answers
60 views

About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
4
votes
1answer
250 views

Enumerating all (super)orientations of an undirected graph

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in ...
2
votes
2answers
290 views

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such ...
1
vote
1answer
251 views

How do I describe this (graph-)problem for a research paper?

I have a function f(x, y) which takes two integers and returns a scalar. My task is to find the set of (x, y) pairs, 0<x<W, 0<y<H where f(x, y)>0, which maximize the sum f(x_i, y_i) ...
1
vote
1answer
212 views

Finding the shortest distance in a dynamic graph

I have a non-weighted directed graph G with edges E and vertices G. Edges can be added or removed, and therefore vertices can be added. For instance, if I have a graph with 4 nodes: 0, 1, 2, 3 and if ...
2
votes
1answer
519 views

Efficient all pair bottleneck computation for a tree

Consider a weighted tree $T = (V,E)$. The bottleneck weight for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). ...
5
votes
1answer
208 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...