# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

881 questions
Filter by
Sorted by
Tagged with
39 views

### How to implement Hopcroft Karp algorithm in CONGEST distributed model?

I've read that one can naively implement Hopcroft-Karp algorithm on a bipartite graph $G=(A,B)$ on $n$ nodes in the distributed CONGEST model in $O(n^{3/2})$ rounds. I've tried doing BFS ...
102 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 ...
88 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 ...
145 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 ...
696 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 ...
80 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 ...
33 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$ ...
22 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 ...
135 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 ...
65 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 ...
40 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 ...
67 views

94 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 ...
127 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 ...
44 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 ...
164 views

29 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 ...
653 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 ...
99 views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

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 ...
64 views

### Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

(This question is inteneded for people who have heard of "Vertex Partitioning Problems" framework of Telle and Proskurowski. Others may dig in only if they are interested in practical ...
157 views

### Minimum vertex cover and odd cycles

Suppose we have a graph G without odd cycles. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, ...
97 views

### How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to ...
94 views

### How to approach the “traveling salesman problem” with cost changing every time salesman reaches a new city

Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. Salesman can go to a different city only on weekends, all ...
60 views

### Reduction graph to planar bounded treewidth and bounded diameter graph

We got reduction graph to planar bounded treewidth graph, but this is unlikely to be true. Let $H$, the planarizing gadget, be planar graph with four distinguished vertices $u,u',v,v'$ on the outer ...
124 views

### Hardness of finding if a vertex lies on a simple directed path between two vertices

Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$? I found a couple of hardness ...
50 views

### Maximum subgraph problem with unknown complexity

Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem: Maximum $Q$-...
47 views

### Efficient game traversal of a DAG of 3-colorings

Let $X$ be a set of size $n$. Consider a game played on board $X$ by two players black and white. Starting with the empty board, each player chooses an empty spot to place a stone. Black moves ...
64 views

### Existence of graphs of every order related to Barnette’s conjecture

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
57 views

### Fast algorithm to find pair of triangles with a common edge in a complete graph

Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles ...
115 views

155 views

### Finding simple fixed length paths in directed graphs

Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?