Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
1
vote
0answers
28 views

Prune length distribution of random binary tree

Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
2
votes
1answer
78 views

Finding the single-crossing embedding of a single-crossing graph

Is it known how to find a (piecewise) straight-line embedding of a single-crossing graph on the plane with exactly one crossing in polynomial time? We are currently trying to come up with a method for ...
-1
votes
0answers
83 views

Expected number of node visits during random walk

Say we have a graph $G = (V,E)$ and all we know about the graph is the degree $deg(n)$ of each node $n$, $|V|$, and $|E|$. Say we begin a random walk of length $l$ starting at a random node. What is ...
2
votes
1answer
139 views

Coloring intersection graph of squares

It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard. What about squares and more specific case "unit squares"? Thanks.
-1
votes
1answer
223 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 ...
10
votes
0answers
270 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 ...
3
votes
1answer
127 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 ...
3
votes
1answer
147 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 ...
4
votes
0answers
79 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 ...
1
vote
1answer
102 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 ...
8
votes
1answer
126 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 ...
0
votes
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 ...
4
votes
1answer
167 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 ...
1
vote
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 ...
1
vote
0answers
47 views

Generalizing PageRank for tripartite graphs

Problem I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...
3
votes
1answer
94 views

Approximating Independent Dominating set on bipartite graphs

I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices. My question is: are there any positive results in the ...
2
votes
0answers
95 views

Graph recovery from pairwise-common neighborhoods

Define the common neighborhood of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the pairwise-common ...
1
vote
2answers
126 views

Maximum cliques of the transitive closure of a chordal DAG

Let $G=(V,A)$ be a directed acyclic graph, for which the underlying undirected graph is chordal (so that every induced cycle in the underlying undirected graph is a triangle). It is known that in a ...
5
votes
0answers
145 views

Minimum spanning tree, but with an unusual objective function

This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem. If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
7
votes
1answer
282 views

STCONN in $O(n)$ time?

This is a very basic question on $s$-$t$-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph $G=(V,E)$ in $O(n+m)$ time and $O(n)$ space, where $n=|...
1
vote
1answer
42 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 ...
2
votes
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 ...
6
votes
2answers
351 views

Is that edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
4
votes
1answer
232 views

Is this edge orientation optimization problem NP-hard?

Is the following optimization problem NP-hard? Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
2
votes
0answers
166 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 ...
2
votes
0answers
78 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 ...
5
votes
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$...
1
vote
2answers
98 views

Name of this graph partitioning problem? (related to coloring)

Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
3
votes
1answer
53 views

Problem conditions to use Laplacian solvers

I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense. Suppose that we want to solve Ax=b, ...
2
votes
0answers
26 views

Pagerank update upon vertex removal

Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges. How to efficiently compute the Pagerank of remaining vertices in the ...
3
votes
1answer
144 views

A stronger Flow Decomposition Theorem?

In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows: Every nonnegative arc flow x can be represented as a path ...
9
votes
1answer
190 views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
-1
votes
1answer
36 views

Multi agent path following with collision avoidance with pre-determined path

I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only. The problem: There is 12x12 grid, with a few solid blockades within them....
0
votes
0answers
29 views

Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph

tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
1
vote
1answer
104 views

Dynamic transitive closure with immediate new reachability facts

The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, ...
3
votes
1answer
109 views

Minimal clique edge cover vs minimalist (assignment-minimum) ones

Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
2
votes
1answer
72 views

Has this bipartite graph problem been studied?

I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon ...
2
votes
1answer
147 views

Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
0
votes
0answers
118 views

Triangle counting using approximate matrix multiplication — suspicious paper

This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper)....
3
votes
0answers
44 views

Counting subsets of bipartite graph part which admit an induced perfect matching

Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
15
votes
0answers
472 views

Linear-time algorithm to test if clique number equals degeneracy bound?

Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique. A well-known bound on the clique number is $\omega\le d+1$, which is ...
9
votes
0answers
130 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. ...
2
votes
0answers
60 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, ...
0
votes
0answers
42 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 ...
2
votes
0answers
118 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 ...
1
vote
1answer
65 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$....
1
vote
0answers
37 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 ...
1
vote
1answer
49 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 ...
2
votes
0answers
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 ...
9
votes
0answers
75 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 ...

1
2 3 4 5
19