Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

-1
votes
0answers
36 views

Does there exist any distributed algorithms for the Minimum Feedback Arc Set Problem

I am wondering if there are any known distributed algorithms for the Minimum Feedback Arc Set Problem. Exact solutions, approximation algorithms, and heuristic approaches all welcome.
-5
votes
0answers
28 views
+50

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 ...
1
vote
1answer
90 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. ...
0
votes
0answers
15 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, ...
0
votes
1answer
68 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 $...
0
votes
0answers
30 views

Existing of Single Center Graph construction Algorithm

I want to construct a graph $G$ with $n$ number of nodes and $m$ number of edges. The construction should leads to a graph with single/double center. But not more than that. If we take $m=n-1$, then ...
1
vote
2answers
126 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
84 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
0answers
82 views

Efficient algorithms for counting $k$-clique subgraphs

Given a graph $G$ with $n >> k$ vertices, what are the fastest algorithms known to count the number of induced subgraphs in $G$ that are $k$-cliques? Are there algorithms that can do better ...
0
votes
1answer
122 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
98 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
52 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 , ...
1
vote
0answers
53 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....
-1
votes
2answers
255 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 ...
3
votes
1answer
163 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
272 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 $\...
7
votes
0answers
206 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 ...
1
vote
1answer
48 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 ...
5
votes
1answer
63 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, ...
14
votes
0answers
176 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 ...
7
votes
1answer
136 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
63 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 ...
2
votes
1answer
134 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
130 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
71 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 ...
3
votes
1answer
216 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} + \...
8
votes
1answer
119 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 ...
4
votes
0answers
83 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
104 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
193 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$,...
0
votes
1answer
84 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-...
7
votes
2answers
173 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 $...
1
vote
0answers
53 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
225 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 ...
1
vote
1answer
150 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
197 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
116 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 ...
0
votes
0answers
40 views

Thresholding technique for Bottleneck Optimization Problems like k-centre, k-suppliers etc

There is a well know thresholding techniques (introduced by Hochbaum and Shmoys in [1]) for bottleneck optimization problems which preprocesses the instance which is a graph whose edges satisfy the ...
3
votes
1answer
76 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). ...
0
votes
0answers
20 views

Optimization of process duration when multiple processes interact

When you have a process composed of multiple steps (e.g., a recipe), where: each step S has a specific duration d(S) steps ...
1
vote
1answer
136 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 ...
5
votes
2answers
170 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
5
votes
1answer
168 views

Is it possible to find a non-cut vertex in O(|V|) time?

Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a cut vertex if removing this vertex with its incident edges from $G$ makes the graph ...
3
votes
1answer
128 views

Does such model exists?

I have a problem on distributed graph, with the following model: 1. There is a Global Graph $G=(V,E)$ 2. There are $k$ computers. 3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph,...
3
votes
2answers
189 views

Generate connected induced subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the ...
5
votes
1answer
257 views

Efficient algorithm for finding directed cycle with smallest average weight

Suppose we have a strongly connected directed graph with non-negative weights on its edges. Is there an efficient algorithm to find the directed cycle with the smallest average weight in the graph? (...
5
votes
1answer
150 views

Fast extraction of the edges of an induced subgraph

Let $G = (V, E)$ be an arbitrary undirected graph and $W \subseteq V$ a subset of its vertices. What is the complexity of the best algorithms for obtaining the edges $F$ of the induced subgraph $H = (...
0
votes
0answers
82 views

Find max weight induced graph in a multipartite graph with one vertex from each part

Consider the follow problem: Input: $G=(V,E)$, a weighted $k$-partite graph with $n$ vertices. Output: $U \subseteq V$, one vertex from each part, maximizing the total weight of the induced graph $...
-4
votes
1answer
183 views

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial [closed]

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open. 2015 arxiv paper claims it is polynomial: Isomorphism Testing for Graphs of Bounded Rank Width ...
2
votes
0answers
30 views

Nearest Common Ancestor on DFS Tree (with Addition of Leaves in DFS Order) on Pointer Machines

What is the complexity status for the Nearest Common Ancestor Problem on Trees in which the leaves are attached to the tree in DFS order ? i.e. Suppose one is visiting a tree T in DFS, and at any ...