Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
-4
votes
0answers
44 views

Mechanism of Howard's algorithm [closed]

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
2
votes
1answer
137 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
0answers
82 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 ...
10
votes
0answers
267 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 ...
-1
votes
0answers
130 views

Removing k vertices to obtain a Cycle Graph

I am not sure if this is a known problem or not. For an undirected graph, $G$ and $k\in N$ we need to decide if there is a subset $S\subseteq V(G)$ of size at most k s.t every connected component in $...
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, ...
-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 ...
26
votes
3answers
787 views

The complexity of determining if a fixed graph is a minor of another

The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic: 1) It appears that there ...
3
votes
1answer
126 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 ...
6
votes
1answer
174 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 ...
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 ...
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
101 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 ...
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 ...
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 ...
10
votes
1answer
255 views

Complexity of unique coloring of graphs

The Isolation lemma of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution ...
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 ...
6
votes
2answers
348 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_{...
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 ...
4
votes
1answer
231 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$...
2
votes
2answers
164 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
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
142 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 ...
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, ...
9
votes
1answer
189 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$ ...
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
2answers
521 views

Algorithms for graph generation given parameters

I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am ...
21
votes
2answers
1k views

Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is ...
8
votes
3answers
335 views

Check if graph stays connected after edge swap

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
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 ...
-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....
10
votes
1answer
2k views

Count $k$-hop neighborhood for every vertex

For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
9
votes
2answers
6k views

How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead. Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
10
votes
2answers
836 views

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

What is the fastest known undirected graph isomorphism algorithm?
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 ...
2
votes
1answer
146 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 ...
13
votes
3answers
2k views

What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
9
votes
2answers
274 views

Something-Treewidth Property

Let $s$ be a graph parameter (ex. diameter, domination number, etc) A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph $G\in \mathcal{...
2
votes
2answers
110 views

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

This question is on "Vertex Partitioning Problems" framework of Telle and Proskurowski. For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the "Vertex ...

1
2 3 4 5
19