New answers tagged

0 votes

Algorithm for creating an esports season schedule

This sounds like an operations research type of problem. Generally, one effective method for dealing with this kind of combinatorial optimization / scheduling problem is to formulate it as an ...
D.W.'s user avatar
  • 159k
3 votes

Will CSR format store the all 0 column?

Most sparse matrix representations are not shape-preserving for all inputs. You have to store the shape of the matrix separately.
orlp's user avatar
  • 13.4k
0 votes

Coding the labyrinth solver

Step 1. Firstly, adjacency list is preferable, since the graph is very sparse. Even if you don't care about memory and running time, using list is more convenient in this specific problem, since you ...
Smylic's user avatar
  • 176
1 vote

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

It depends on the order of the children. It is usually the case that children in rooted trees are browsed from left to right. Also, if the DFS is written recursively, then this is indeed the correct ...
Nathaniel's user avatar
  • 15.5k
15 votes
Accepted

Can every spanning tree result from a depth-first search?

Consider a complete graph $K_n$. Then a depth-first search can only create a linear-path spanning tree, no matter what the edges processing order is.
Nathaniel's user avatar
  • 15.5k
1 vote

Assigning classes to nodes in a graph to minimise intra-class distance

For the hardness proof, you can look into graph coloring (or its variants). Here's a possible hint: Once you prove it is NP-hard, using ILP is not a bad idea. There are various techniques you can ...
codeR's user avatar
  • 565
0 votes

Combinatorial Optimization Assignment Problem as Graph Coloring Problem

This "answer" probably doesn't answer the question and might not be surprising, but it may be helpful to know in designing algorithms for the problem. Lemma 1. The problem is strongly NP-...
Neal Young's user avatar
-1 votes

Simple graph canonization algorithm

My understanding is that there is a quasi-polynomial time algorithm for graph isomorphism but subgraph isomorphism is np-complete.
IsoCurious's user avatar
7 votes
Accepted

Is determining the existence of a Hamiltonian cycle in a chordal graph NP-hard?

It's NP-complete even on split graphs. For questions like this, always refer to the graph classes website. Chordal graphs at graph classes.org.
Pål GD's user avatar
  • 16.1k
4 votes
Accepted

graph theory single bar vs double bar size notation

You are correct. $|G|$ denotes the number of vertices in $G$, and $||G||$ denotes the number of edges in $G$. Formally, for a graph $G = (V, E)$, $|G| = |V|$ and $||G|| = |E|$. For instance, consider ...
Ziad Ismaili Alaoui's user avatar
2 votes

Weisfeiler-Leman Algorithm

No, because you don't actually get a mapping between graphs (at least not vertex-to-vertex mapping, but you do get a mapping between automorphism groups). As always with the Weisfeiler Leman graph ...
Pål GD's user avatar
  • 16.1k
2 votes
Accepted

An "edge-spanning-tree" of minimum height

Here is an idea. The root of your desired tree should be one of the centers (a vertex with minimum eccentricity) of the graph $G$. You run BFS from each of the nodes in $G$ and observe the resulting ...
codeR's user avatar
  • 565
0 votes

Dijkstra's shortest path algorithm without relaxation

Yes, Dijkstra's algorithm without relaxation is possible. But the big-O complexity is the same. Dijkstra uses greedy strategy so there is the priority_queue that guarantees the popped vertex is the ...
loohooloo's user avatar
2 votes

Graph labyrinth solving sequence

Let $G_1, \dots, G_m$ be an enumeration of all strongly connected directed graphs on at most $n$ vertices in which every vertex has out-degree 2 (the corresponding edges labelled $a,b$). The algorithm ...
Yuval Filmus's user avatar
1 vote

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

All the solutions for $w$ the weight function on the (vertices of the) tree $T=(V, E)$ can be obtained combining Mahyar's and Nathaniel´s answers in this way: Pick any arbitrary numbers $S$ and $S'$. ...
Pablo H's user avatar
  • 211
4 votes
Accepted

Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

[EDIT: updated answer to apply to directed acyclic graphs.] Lemma 1. This problem is equivalent, under approximation-preserving poly-time reductions, to Maximum Independent Set in undirected graphs. ...
Neal Young's user avatar
1 vote

How to find largest caterpillar in a tree

Hint: the heaviest caterpillar that can be formed by a path starting at a node and moving strictly downward in the tree (its down-weight) is the down-weight of the heaviest non-leaf child if it ...
orlp's user avatar
  • 13.4k
0 votes

Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST

There is a proof on the internet without distinct edge weights assumption found in this document from flashmt's comment in codeforces. It is the equivalent of the proof provided, only written more ...
Kenneth Kho's user avatar
1 vote

How to find smallest n so that all walks of length greater or equal to n include set of paths

Current problem is $\mathrm{NP}$-hard, because directed Hamiltonian path problem can be reduced to the current one. (Taking the same graph with empty set of forbidden paths, or adding some new arcs ...
Smylic's user avatar
  • 176
1 vote
Accepted

Proving that Breadth-First Search (BFS) results in a bipartition of a tree

Let $r$ be an arbitrary root. Denote by $d(v)$ the distance from $r$ to $v$. As you might know, every edge goes either between vertices of the same layer, ie, vertices of same $d(v)$, or between ...
Pål GD's user avatar
  • 16.1k
9 votes
Accepted

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

Using the idea of @Mahyar, I think there is another way to find a solution to the problem. Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). ...
Nathaniel's user avatar
  • 15.5k
8 votes

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

We can weight vertices such that the entire tree has a fixed sum of weights; for example, zero. Let us design a recursive procedure that assigns weights to the vertices of a tree $T$ with root $r$ ...
Mahyar's user avatar
  • 81
0 votes

Path Through Graph That Minimizes Node Attributes

It's NP-hard with a single source and a single target, and looking for a single path. Reduction from SAT. Let $\phi = C_1 \land C_2$ where $C_1 = x \lor y$ and $C_2 = \neg x \lor y$. See attached ...
Pål GD's user avatar
  • 16.1k
3 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Group theory is used all over the place in quantum computing. Some examples: The set of reversible quantum logic gates on $n$ qubits is the group $SU(2^n)$. Some important finite groups of quantum ...
shashvat's user avatar
  • 131
3 votes
Accepted

Shortest paths in $k$-partite DAG

If $|p_k|\leqslant N$ for all $k\in \{1, …, |P|\}$, then a dynamic programming algorithm can compute all those distance in $\mathcal{O}(|V|^2\times N)$ which could be lesser than $|V|^3$. The idea is ...
Nathaniel's user avatar
  • 15.5k

Top 50 recent answers are included