Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
981
questions
0
votes
0
answers
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 ...
- 139
1
vote
1
answer
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
0
answers
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 ...
- 139
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 139
0
votes
0
answers
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
2
votes
1
answer
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
2
votes
1
answer
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
1
answer
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
0
votes
0
answers
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:
\begin{equation}
\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
2
votes
1
answer
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
0
votes
0
answers
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
5
votes
1
answer
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
2
votes
0
answers
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
0
answers
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
3
votes
1
answer
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
0
votes
1
answer
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
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 1
-1
votes
1
answer
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)$...
- 49
6
votes
1
answer
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
10
votes
0
answers
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
0
answers
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
0
answers
45
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
-3
votes
1
answer
151
views
Finding a path in a graph hitting a particular vertex
Problem: Given three vertices $u, v$ and $w$ from an undirected graph. Find a path (where vertices are not repeated) from $u$ to $w$ that passes through $v$. This problem has been mentioned in ...
0
votes
0
answers
51
views
Steiner Tree Problem for circle graph
Can Steiner Tree Problem be solved in polynomial time on circle graph?
- 11
0
votes
0
answers
43
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 547
3
votes
1
answer
188
views
Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?
Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?
I read abstract of this paper that mentioned an algorithm with running ...
- 194
3
votes
2
answers
191
views
exact path cover for undirected graph
In a Python plotting application,
I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path.
The number of ...
- 149
5
votes
0
answers
83
views
Fine-Grained Hardness for Undirected Hamiltonicity
The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time.
However, for undirected graphs on $n$ nodes, there is an ...
- 454
3
votes
0
answers
113
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 454
2
votes
0
answers
100
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
- 683
1
vote
1
answer
190
views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
- 153
0
votes
0
answers
51
views
Minimal lexicographical path on DAG in O(||V| + |E|)
Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest ...
2
votes
1
answer
104
views
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Consider the node-weighted steiner problem:
Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \...
- 547
4
votes
1
answer
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 ...
- 683
2
votes
0
answers
93
views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
- 4,631
0
votes
0
answers
105
views
Does this sum-product algorithm make more sense?
Recall the belief propagation "sum-product" algorithm (from wikipedia):
$\forall x_v\in Dom(v),\;$
$\mu_{v \to a} (x_v) = \prod_{a^* \in N(v)\setminus\{a\} } \mu_{a^* \to v} (x_v)$
$ \mu_{...
- 129
6
votes
0
answers
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
5
votes
2
answers
260
views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
- 103
1
vote
1
answer
101
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 547
1
vote
0
answers
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 ...
3
votes
1
answer
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
2
votes
1
answer
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
-2
votes
1
answer
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
10
votes
0
answers
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
3
votes
1
answer
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
3
votes
1
answer
153
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 ...
- 407
4
votes
0
answers
83
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,035