Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

1
vote
1answer
102 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
120 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
132 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 ...
2
votes
1answer
117 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
165 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
217 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
137 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
72 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 ...
-5
votes
1answer
151 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
28 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
87 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
113 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
83 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
252 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
159 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
49 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
375 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
42 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
58 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
37 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
339 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
36 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
123 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
89 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
123 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
116 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
171 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
114 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
355 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
138 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 ...
2
votes
1answer
513 views

Longest path in a DAG that's not too long

The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is ...
2
votes
1answer
108 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
0
votes
0answers
88 views

Adversarial Search Algorithms

What are the best adversarial search algorithms? I understand that this may seem like a subjective question. However, I am asking for what situations are different algorithms best for. In particular, ...
2
votes
0answers
64 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
4
votes
1answer
103 views

Minimum weight matching in general graphs with additional input specifying the number of matched edges

We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of ...
0
votes
0answers
62 views

Find the number of vertices that belong to all the maximum matchings of a general connected graph [duplicate]

The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well. An O(VE) ...
2
votes
0answers
25 views

centralized deterministic Spanner construction with low degree and low stretch

Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
12
votes
1answer
285 views

Gentle introduction to the algorithmic aspects of tree-depth

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and ...
4
votes
0answers
77 views

Graph factors of maximum weight

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of ...
0
votes
2answers
283 views

Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
11
votes
2answers
363 views

Number of vertices present in all maximum matchings

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. Is there a solution beside the obvious remove ...
2
votes
1answer
99 views

Finding a random regular graph with degree d

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$. For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
1
vote
1answer
103 views

Finding all possible simple cyclic paths in a digraph

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is ...
4
votes
0answers
80 views

Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

Let $G=(V, E)$ be an undirected simple graph. Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
5
votes
0answers
141 views

Statistical Algorithms vs Convex Relaxations - Planted Clique

I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
0
votes
2answers
101 views

Finding a set of hubs in a graph

Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source ...
0
votes
1answer
68 views

Length bounded minimum cardinality cut in DAGs

Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum ...
7
votes
1answer
186 views

Embedding a graph in the euclidean space

Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the ...
0
votes
0answers
42 views

Approximate distance preserving sparse graph representation that are not necessarily subgraphs

I am looking for a type of graph sparsifier that I think I have seen somewhere but now I can't find the paper anymore. I think the paper referred to it as a spanner, but that term is used for so many ...
3
votes
2answers
225 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...