Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

3
votes
0answers
16 views

On bandwidth of graphs

I am trying to find references studying uses of graph bandwidth in algorithms, in the same way as it is done with tree-width for instance. I could only find research related to computing the ...
3
votes
0answers
32 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 ...
1
vote
1answer
65 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 ...
4
votes
0answers
40 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). ...
1
vote
0answers
66 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
206 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
116 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
82 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
97 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
189 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 ...
0
votes
1answer
73 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 ...
7
votes
2answers
165 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
50 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
219 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
106 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
194 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
115 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
73 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
129 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
168 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
160 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 ...
3
votes
2answers
181 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 ...
4
votes
1answer
242 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
142 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
176 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
29 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 ...
2
votes
1answer
95 views

Algorithms for tree rotation

What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest ...
1
vote
0answers
118 views

Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region ...
2
votes
0answers
104 views

Shortest non-crossing geometric paths

I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
5
votes
1answer
254 views

complexity of graph 2.5-coloring

My question is inspired by this one. ​ I define 2.5-coloring to be the parameterized problem Instance: an integer j and an n-vertex non-empty simple graph G Parameter: integer k Output: if there is ...
13
votes
1answer
160 views

2FA state complexity of k-Clique?

In simple form: Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states? Details Of interest here are $v$-vertex graphs encoded using a sequence ...
-1
votes
1answer
64 views

Reconstructing a 2D lattice graph from an unordered adjacency list

Is there any kind of algorithm that can map a set of points and their unordered adjacent neighbours to a 2D lattice graph that would then be addressable using X, Y coordinates? For example, given the ...
15
votes
2answers
469 views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...
0
votes
1answer
43 views

Minimal-size extending set in a directed graph

Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$. We call a subset $J\subseteq V$ extending if for every $v\in V\setminus J$ there is a directed path from some ...
0
votes
0answers
65 views

What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by ...
0
votes
0answers
41 views

How to find all alternating cycles wrt. a perfect matching?

Given an undirected graph $G$, Tarjan's bridge finding algorithm gives me the set of all bridges (edges that do not occur in any cycle) in $G$ in linear time. Now, I have a perfect matching $M$ in ...
7
votes
1answer
421 views

Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
0
votes
0answers
38 views

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
1
vote
0answers
127 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
5
votes
1answer
90 views

Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$. The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in ...
3
votes
1answer
132 views

Maximum size-k cut

Here's my problem, Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and ...
2
votes
2answers
120 views

Favorable graph decomposition for dense graphs to solve independent set problem

I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or ...
10
votes
1answer
184 views

Minimum equivalent digraph with respect to sources and sinks

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$. Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that: For all pairs $u \in S, v \in T$ ...
2
votes
1answer
121 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
15
votes
1answer
394 views

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
-3
votes
1answer
155 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...