New answers tagged

0

After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected deterministically so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not ...


1

A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1]. You can also prove yourself that this problem is NPC by a straightforward ...


3

This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


4

A result about BFS is that what you call the depth of the BFS of a node $v$ is the length of a shortest path from the source to $v$. Assume the exists an instance where the depth of the DFS $<$ BFS. Then we have a path from the source to $v$ that has length strictly smaller (the path taken by the DFS to reach $v$) than the length of a shortest path from ...


2

No. In a graph with $n$ nodes, Dijkstra's algorithm never updates a node more than $n-1$ times, so your test will never change anything. More fundamentally, negative-weight edges or cycles don't cause Dijkstra to get into infinite loops; they just make it give wrong answers in some cases. This answer on Stack Overflow gives more detail.


7

Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected. Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_v$ for $v \in V$: $x_{v_0}$. For every $(u,v) \in E$, $\lnot x_u \lor x_v$ and $\lnot x_v \lor x_u$. $\bigvee_{v \neq v_0} \lnot x_v$. Here is a SAT instance which ...


0

The idea is to use dynamic programming. For each vertex $v$ and color subset $S$, calculate whether there is a simple path, ending at $v$, and including exactly the colors in $S$. Details left to you. The main trick here is that we can be sure that the path being constructed is simple since all vertices in it have different colors. We can apply the same ...


2

Some old results by Vladimir Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165-176, imply that Question 3 has an affirmative answer. Although the auxiliary graph is not assured to be in some way as elegant or natural as in the case of line graphs or their squares. The easiest example that I can come up with has 13 times the ...


0

Yes, this is sort of common subexpression elimination. Simple approach for binary trees: introduce nodes 1 for a ... 6 for f. Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it. You will need unordered map from pair of nodes to node, representing this pair: (...


4

Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$. A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas. Each edge must have exactly one color: At least one color, for each $e \in E(G)$: $(x_{e,1} \vee x_{e,2} \...


2

Counter example: V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}. A MST of this graph, rooted at a, could be: {(a,b), (a,d), (b,c)}. But this is not a SPT because the path a->c is of length 2 instead of 1 (a and c are directly connected in the original graph).


0

Shortest-path tree is defined for a graph and a root vertex. Edit: My previous example was for a weighted graph, but still you can find counter-examples by choosing the root vertex carefully.


1

Since I don't have enough points for a comment: This problem is not going to have a very efficient solution. Looking at the $k=3$ case should be good start. In this case one can solve this problem with $O(|E|)$ space by keeping an (online) adjacency set for each vertex and when an edge $(u,v)$ arrives comparing the adjacency sets of vertices $u$ and $v$ for ...


0

Let f be a function from the color set of the first tree to the color set of the second tree. The function f is initially defined only partially, for e.g. that f(color(root of first tree)) = color(root of second tree). At each node of the tree, isomorphism is checked by trying both ways of mapping its children and checking whether the sub tree rooted at ...


0

Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies $$ |A(G) - \alpha(G)| \leq K, $$ where $\alpha(G)$ is the maximum size of an independent set in $G$. We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the ...


Top 50 recent answers are included