All Questions
Tagged with combinatorial-optimization graph-theory
134 questions
0
votes
0
answers
24
views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1
0
votes
1
answer
51
views
Cycle-Sculpturing with Minimal Vertex-Deletion
given a simple, finite and symmetric graph $G(V,E)$ with $n$ vertices and at least $n$ edges
Question:
how can the smallest set of vertices $W\subset V$ be calculated for which the graph induced by $...
- 13.2k
1
vote
0
answers
54
views
Finding a path of given length with maximal relative weight
Let $G$ be a directed graph with vertices $V$ and edges $E \subset V\times V$. A path of length $n \geq 2$ in $G$ is a sequence of vertices $(i_{0},i_{1},\ldots,i_{n-1})$ such that $(i_{k},i_{k+1}) \...
- 798
1
vote
0
answers
48
views
How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched
Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance.
The gist of the problem is as follows:
I have two ...
3
votes
0
answers
147
views
Understanding why $\frac{\phi^5}{2}$ solves this 3D optimization problem, where $\phi$ is the golden ratio
I would like to understand the deep meaning of a solution which arises from an optimization problem discussed in a paper of mine since it can be simply stated as $\frac{\phi^5}{2}$, where $\phi := \...
- 1,451
3
votes
2
answers
336
views
Algorithm to evaluate "connectedness" of a binary matrix
I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...
- 1,000
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
2
votes
1
answer
112
views
Finding survivable paths with a set of vulnerable edges
Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ ...
- 367
8
votes
1
answer
567
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 1,451
0
votes
0
answers
123
views
A variant of Steiner tree
Consider a directed Steiner tree problem with a source node $s$ a set $T$ of terminals with the following constraint. For each node $v$ on the tree, we assign a branching value $b_v$ as follows. (1) $...
- 367
1
vote
0
answers
88
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
5
votes
1
answer
383
views
Shortest polygonal chain with $6$ edges visiting all the vertices of a cube
I am trying to find which is the minimum total Euclidean length of all the edges of a minimum-link polygonal chain joining the $8$ vertices of a given cube, located in the Euclidean space. In detail, ...
- 1,451
4
votes
0
answers
229
views
Optimal colorings
If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...
- 48.9k
5
votes
2
answers
557
views
What is the proper name for this "tersest path" problem in Infinite Craft?
The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...
- 677
1
vote
0
answers
157
views
Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$
After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...
- 1,451
2
votes
1
answer
152
views
First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem
Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...
- 1,451
0
votes
0
answers
16
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
- 21
0
votes
2
answers
139
views
Graph vertices selection for paths sum minimalization
Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...
6
votes
1
answer
374
views
Desargues ten point configuration $D_{10}$ in LaTeX
I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
- 41.8k
2
votes
2
answers
112
views
Real-world datasets for testing the maximum edge bi-clique problem
We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
- 23
1
vote
0
answers
41
views
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.
Given a graph $G = \{V,E\}$,
we have a distance matrix (the ...
- 11
0
votes
0
answers
126
views
On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph
Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
- 61
0
votes
0
answers
57
views
Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph
This is about graph theory.
Define an h-dimensional hyperedge as a set that contains h vertices.
A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
- 23
1
vote
0
answers
63
views
A multi-layer version of Menger's theorem
Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...
- 1,926
3
votes
0
answers
111
views
The matrix representation of an interval graph
It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
- 4,049
3
votes
1
answer
240
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 33
0
votes
0
answers
118
views
Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point
In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
- 1,451
3
votes
0
answers
190
views
Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree
We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$.
In a sequential fashion, we select ...
- 1,677
1
vote
1
answer
536
views
Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$
Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared ...
- 1,451
0
votes
1
answer
79
views
Dual equivalence of minimum feedback-vertex sets and cycle packing
it is known that the duals of feedback-set problems are set-packing problems; in the context of digraphs the feedback set are either a minimal set of vertices or edges that hit every oriented cycle; ...
- 13.2k
0
votes
0
answers
50
views
Can we talk about approximation when the decision problem for solution existence is NP-Hard
I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
1
vote
0
answers
65
views
Find a cut of a graph that minimizes the ratio between the edge weights of the cut and the edge weights inside one subgraph
Given an edge-weighted undirected graph $G=(V,E)$ (can assume the weights are non-negative) and a source node $v_s\in V$, a cut is a partition of $G$'s vertices into two complementary sets $S$ and $T$....
- 143
2
votes
1
answer
255
views
Can connectivity be less than min cut/degree?
Suppose we have a graph with min-cut $\lambda$ and minimum degree $> \lambda$.
Is it possible for there to be a vertex that is at most $\lambda$-connected to every other vertex in the graph?
...
- 23
1
vote
2
answers
107
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 13
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
2
votes
0
answers
63
views
Maximize connectivity probability with a number of edges
We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
- 367
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
1
vote
0
answers
45
views
Vertex cover via maximally unbalanced spanning trees
The vertex cover problem asks for a smallest subset $U\subseteq V$ that is adjacent to all edges of a symmetric graph $G(V,E)$.
Inspired by the observation that led to this question Perfectly balanced ...
- 13.2k
5
votes
1
answer
171
views
Graph combinatorial optimization problem
Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. ...
- 1,677
1
vote
1
answer
165
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,677
5
votes
1
answer
429
views
Menger's theorem with restrictions on where the paths can begin and end
Let $k\in\mathbb N$. Given a finite graph with two subsets of vertices $X$ and $Y$, Menger's Theorem gives a criterion for when there are $k$ pairwise disjoint paths starting in $X$ and ending in $Y$.
...
- 1,644
2
votes
1
answer
138
views
Generating short Hamilton cycles from complete graphs
Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.
A vertex ...
- 13.2k
0
votes
0
answers
55
views
Does LKH perform best with $\mathrm{1\unicode{x2013}trees}$
The LKH heuristic essentially generates sequence connected graphs with $n$ edges by means calculating minimum-weight spanning trees of $n-1$ of the vertices and connects the unspanned vertex to the ...
- 13.2k
7
votes
1
answer
171
views
Metric TSP with integer edge cost
Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
- 367
0
votes
0
answers
52
views
What do optimal tours tell about finite point sets?
Let $T_{\mathrm{MIN}}$ and $T_{\mathrm{MAX}}$ denote the shortest, resp. longest Hamilton cycle through a set of $n=2k+1$ points.
Let further $S_{\mathrm{MIN}}$ and $S_{\mathrm{MAX}}$ be the "...
- 13.2k
0
votes
0
answers
36
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
- 171
3
votes
1
answer
325
views
Is anything written about winning the "Dollar Game" in the minimal number of moves?
I run some Master's projects on Chip-Firing games, using the Holly Krieger's Numberphile video on the topic as an initial motivation, and going on to prove the main theorem stated there (that you can ...
- 2,372
2
votes
1
answer
272
views
Minimizing the degree of outgoing edges in a digraph, does this problem have a name?
I have a problem which can be rephrased in this way.
Suppose $G = (V,E)$ is a digraph (directed graph) and for each $v \in V$ we denote with $\delta^+(v)$ the number of outgoing edges of the vertex $v$...
- 115
4
votes
2
answers
304
views
High degree differences in bipartite graphs
Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:
$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
user153000
1
vote
0
answers
168
views
Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph
A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
- 1,190