# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

906 questions
Filter by
Sorted by
Tagged with
21 views

### Maximal alpha beta pruning [closed]

I have found a question in a book about tree searching algorithms and i would like to know the right answer: Consider a Tree with depth 3 and all vertices have an degree of 3. How many vertices are ...
48 views

### Why does the ball growing procedure of Even etal  not work for directed multicut?

Why does the ball growing procedure of Even etal  "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" not work for the directed multicut problem considered in e.g &...
107 views

### Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

Planar graphs are 4-colorable. Determining if a planar graph is 3-colorable is NP-Complete. A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable. ...
51 views

### Can we always find a graph with a given algebraic connectivity?

This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong. I would like to experiment with various spectral properties of graphs, ...
33 views

### Gradient descent on k nearest neighbor graph

I wanted to know how gradient descent can be used to minimize the distance function in approximate k nearest neighbor algorithm as mentioned in paper "Efficient K-Nearest Neighbor Graph ...
29 views

### algorithms for finding (perfect) b-matching

Given a k-partite graph $G=(V,E)$ we are interested in finding a (perfect) b-matching. That is, we want a subset $S \subset E$ (of maximal cardinality) s.t. every vertex $v \in V$ is contained in at ...
115 views

### Finding nodes with enough unique ancestors

Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
58 views

### Separating DAGs using separators consisting of lists of nodes and all ancestors

Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
36 views

### Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
33 views

### Best approximations of Minimum Dominating Sets in chordal graphs

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime ...
15 views

### Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
67 views

### Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
59 views

65 views

### Calculation of sum of weights of nodes in a tree graph

Updated There's a real production project related to real estate properties around the world. The data has a structure of nested nodes. E.g. end nodes which have no outgoing edges (red) are properties ...
135 views

### Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism. By ordered I mean that each vertex has a list of ...
77 views

107 views

### Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
101 views

### Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
162 views

### Topological sorting of a DAG where special vertices have to come in even groups

Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
711 views

### Algorithm for finding a 3-cycle cover

Given: An undirected, unweighted graph Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges Is there any algorithm that solves this problem, possibly with some ...
88 views

### NP-Hard or PTIME?

I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
34 views

### Efficient algorithm for finding segregators in a directed acyclic graph

Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
25 views

### Are the intermediary sets in maximum cardinality search optimal in some way?

The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
141 views

### How to efficiently find a loop between two nodes in a directed graph?

Given two nodes in a directed graph, how can I find a loop (if exists) that pass these two nodes? The loop cannot pass a node more than once. And if there isn't such a loop, how to efficiently ...
72 views

### Uniformly sampling or counting connected graph partitions with any number of blocks

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ...
45 views

### Incremental PDA emptiness testing?

Is there anything known about the problem of incremental emptiness testing for a pushdown automata? Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
71 views

124 views

### Reference request: Depth- (or Breadth-) first search with hints?

Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it. Would it be possible to pre-process the graph and ...
135 views

### Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
96 views

### Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle). For example, given the adjacency matrix: ...
76 views

### Variation of edge-disjoint spanning trees

In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing ...
167 views

41 views

### Minimum rank graph cut

Consider the following problem: Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle. Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
970 views

### Sequential vs Distributed algo question

If a certain graph problem in the $\textbf{sequential}$ setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this ...
We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover. Let $G$ be connected simple graph. $k$-clique cover of graph $G$ is partition ...