Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
881
questions
-1
votes
0answers
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 ...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
5
votes
2answers
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 ...
7
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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$ ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
67 views
3-dimensional matching variant
In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\...
3
votes
1answer
110 views
What is the complexity of this weighted b-edge matching problem?
I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:
Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,...
1
vote
1answer
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 ...
7
votes
0answers
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 ...
-4
votes
1answer
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:
...
2
votes
0answers
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 ...
8
votes
0answers
164 views
Sublinear time path existence
Consider a graph $G = (V,E)$ with $N$ edges. Consider two vertices $u_1, v_1 \in V$. We wish to find whether there exists a path of length $4$ between these two vertices or not. This is easy to do in $...
10
votes
0answers
138 views
Alternative proofs of Savitch's theorem?
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?
By the usual one I mean the proof based on recursively querying whether there is a midpoint.
...
1
vote
1answer
56 views
Reachability Query for Tree
What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $...
1
vote
0answers
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 ...
-2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
-2
votes
1answer
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}$, ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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$-...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
9
votes
2answers
115 views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
7
votes
0answers
141 views
Algebraic methods for testing planarity
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
6
votes
1answer
207 views
Complexity of finding the largest induced subgraph with all even degrees
What is the complexity of the following problem?
Instance: Simple, undirected graph $G$, and a positive integer $k$.
Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
10
votes
1answer
713 views
Relationship between two graph optimization problems
Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph:
P1. Find a largest induced subgraph of the ...
9
votes
0answers
136 views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
8
votes
0answers
127 views
Is APSP verification easier than APSP?
In APSP, the input is an $n$-node directed weighted graph $G$, and the output is an $n \times n$ matrix holding pairwise shortest path distances between nodes in $G$. Define "APSP-Verification" as ...
2
votes
1answer
95 views
Diameter vs. Tractability
I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2):
1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge ...
1
vote
1answer
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?
0
votes
1answer
99 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
9
votes
2answers
302 views
How long does it take to find a short cycle in a random graph?
Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
10
votes
2answers
224 views
“Relatives” of the shortest path problem
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
3
votes
0answers
147 views
Enumerating Minimal (a,b) vertex separators in a DAG
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.
$S$ is a ...
2
votes
1answer
120 views
Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free
What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs ...
6
votes
1answer
230 views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.
There is also a parameterized algorithm for ...
1
vote
0answers
88 views
Shortest s-t Path with a covering constraint
Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
9
votes
1answer
266 views
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
2
votes
0answers
78 views
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
I have encountered an interesting problem that I couldn't find any references to solve:
Determine the smallest subset of nodes that
need to be removed from an undirected graph to make it a tree.
...
