People who code: we want your input. Take the Survey

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
0answers
28 views

### end node with unique path length from the start node in a DAG

Let $G(V,E)$ be a directed acyclic graph with all edge weights set to one and $s\in V$ be the start node, $E \in V\backslash s$ be the set of end nodes. My problem is to find an end node $e\in E$ ...
0answers
39 views

### 3-hitting set iterative compression

I have a question which i tried to solve without success. I need to prove that if 3-Hitting Set can be solved in time $2^kn^{O(1)}$,then 4-Hitting Set can be solved in time $3^kn^{O(1)}$. There is a ...
0answers
39 views

### Claw-free graph linear kernel [closed]

I'm having a hard time solving the problem below: In Claw-free problem, we are given a graph G and $k$, and the objective is to decide whether there exists a subset S $\subseteq$ V (G) of size at most ...
0answers
25 views

### Randomized algorithm for finding Minimum feedback vertex set

Algorithm FVS(G, k): If k < 0, return ”NOT FOUND” If G is acyclic (i.e., a forest), return  While there exists a vertex 𝑢 of degree at most 2: If deg(u) = 1, remove u If deg(u) = 2, i.e. u's ...
1answer
210 views

### Find research partner (profession and beginner)

I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program. Now, I've ...
0answers
177 views

### Finding uniformly random perfect matching of a graph

Problem: Suppose that we have a graph $G$ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
1answer
122 views

### Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...
1answer
145 views

### TSP with “enemy” nodes

I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for. The story/idea ...
0answers
78 views

### Flipping one bit to maximize BMM output

Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
1answer
93 views

### Finding output with unique witness in matrix multiplication

Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication ...
1answer
118 views

### Finding vertex separator such that the induced subgraph has minimal number of edges

My problem is related to edge and vertex cuts with a little twist. Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
0answers
51 views

### Efficiently checking if removing a vertex yields a connected partition

Having seen the answer here, I have been looking at the algorithm suggested by Chlebikova (1996). The algorithm needs an implementation of the blockbalance algorithm which requires that one repeatedly ...
1answer
163 views

### Does such a bipartite graph exist?

In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
0answers
31 views

### Latest results on the k-stacker crane problem?

I was searching for the $k$-stacker crane problem on google scholar but the best known result is dated back to 1976 with the original paper. I'm unsure whether there would be newer results of the ...
0answers
45 views

1answer
40 views

### Bipartite graph projections, with threshold

Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$. The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
1answer
34 views

### Maximum weight matching with classes of edges in a multi-edge bipartite graph

Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here. Consider a ...
2answers
341 views

0answers
163 views

### Is this node permutation optimization NP-Hard?

Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
0answers
77 views

### Dynamic connectivity with known history, for maximal connected component span

Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
0answers
164 views

### Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

This problem came up in my study of digraphs: Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$. Note that $A$...
2answers
95 views

1answer
72 views