2022 Developer Survey is open! Take survey.

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

981 questions
Filter by
Sorted by
Tagged with
17 views

### Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems. The Shortest Steiner cycle problem is defined ...
1 vote
40 views

### Question about algorithm for enumerating minimal AB-separators

Let $A,B\subseteq V(G)$ be two non-adjacent, disjoint subsets of vertices in $G$. A subset $S\subseteq V(G)\setminus (A\cup B)$ is an $AB$-separator if the graph $G[V\setminus S]$ contains two ...
• 45
1 vote
39 views

### Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?

The shortest $k$-edge disjoint paths problem is defined as follows: Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Find (if exist) $k$-pairwise ...
1 vote
49 views

### Cheapest Insertion is $2$-approximation for TSP

Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
39 views

### Is Power Dominating Set in W[2]?

I'm interested in the Power Dominating Set problem: given a graph, find a power dominating set $D$ of size at most $k$. A power dominating set is a set of vertices such that it "observes" ...
• 419
64 views

### Does the Christofides algorithm ensure this inequality?

Let $(X,d)$ be a finite metric space. Let $C$ be a Hamiltonian cycle (over $X$) outputted by Christofide's algorithm. Also, let $K$ be a minimum spanning tree. I am aware that Christofide's algorithm ...
55 views

### Parameterized Complexity of Vertex Multicut

Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
• 45
112 views

### Is the center of a BFS tree a good approximation of the graphs center?

Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$). Finding the center of the graph can easily be done using all-pairs-shortest-...
• 21
95 views

### Proving a property of minimal st-separators that are not minimum st-separators

Let $G$ be an undirected, connected graph, and $s,t$ non-adjacent vertices in $G$. Denote by $k_{st}(G)$ the $st$-connectivity of $G$. That is, $k_{st}(G)$ is the size of any minimum $st$-separator of ...
• 45
1 vote
139 views

### Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
• 454
38 views

### Reducing computing the partition function to computing the number of min-cardinality (s, t) cut

Consider a partition function for a graph as follows: \mathrm{Z}_\mathrm{G}(\beta) = \sum_{z \in \{-1, 1\}^{n}} \beta^{\underset{(i, j) \in E, i < j}{\sum} w_{i,j} ~z_i z_j}, \end{...
• 153
125 views

### Parameterized algorithm when the parameter is not known in advance?

In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter. However, it seems like in applications the value of the parameter should ...
• 547
46 views

### Breaking ties in A* to produce same path as D*lite

What tie breaking criteria do I need to implement in A* to mimic exactly the same behaviour as D* lite. Ofcourse both algorithms use the same heuristic and cost functions. So basically if I run A* ...
• 9
153 views

### Is there a standard axiomatization of graph width parameters?

There are many useful graph properties described as "width parameters" that show up in algorithm analysis (especially for FPT-type algorithms). The most famous example is probably treewidth,...
• 2,183
54 views

### Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?

Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions? No edge touches vertices other than its end vertices. At any ...
1 vote
168 views

### Easier famility of graphs for MAXCUT [closed]

I would like to know if there are particular family of graphs for which the Goemans-Williamson MAXCUT Approximation Algorithm renders higher than 0.878 approximation ratio. TIA
• 997
100 views

### Proof of SPFA's worst-case complexity?

I am trying to prove the worst-case asymptotic time complexity of the Shortest Path Faster Algorithm (SPFA). I know the complexity is the same as the "original" Bellman-Ford (BF) algorithm, ...
• 33
72 views

### Is a grid graph a vertex-minor of a complete graph? [closed]

Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
• 153
55 views

### Fastest algorithm to compute maximum number of boxes that can fit inside each other

Given $n$ rectangles with widths $w_1,w_2,...,w_n$ and heights $h_1, ..., h_n$. A rectangle $i$ fits inside $j$ if and only if $h_i<h_j$ and $w_i<w_j$. We are interested in the maximum $k$ such ...
• 680
92 views

### optimization on graph edges selection

I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there. I am ...
241 views

### Does such a graph exist? [closed]

[EDITED FOR CLARITY] Does there exist an edge-colored graph $G$ with the following properties? $G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
313 views

### Complexity of optimal elimination for a planar tensor network

Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question Suppose we need to sum out variables in a tensor network (a factor graph where each ...
• 4,631
128 views

### Fastest Known Algorithm to Count Acyclic Orientations in a Graph

Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
• 454
1 vote
72 views

### A reduction from the maximum $k$-closure problem to the clique problem

Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
• 111
1 vote
45 views

• 547
358 views

### Pagerank in directed *acyclic* graphs (DAG)

I deal with pagerank computations on large directed acyclic graphs (DAG). I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
93 views

• 129
191 views

### Fastest exact algorithm for MAXCUT

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
• 997
260 views

• 547
1 vote
51 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 ...
101 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 ...
• 175
158 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.
• 21
315 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 ...
• 45
285 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 ...
• 101
169 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 ...
• 133
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 ...