Find an edge subset such that the graph is bipartite.
$begingroup$
Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit.
Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges.
I already know that a graph is bipartit if they do not contain a cycle with an odd number of nodes.
I am also aware that it is possible to decide whether a graph contains a circle and whether it has odd number of nodes in linear time using Depth-First Search.
The problem is that this only findes a cycle and not all.
Is this approach even right and if yes how do I need to adapt it and if not what would be a better approach?
graph-theory bipartite-graph
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
$endgroup$
add a comment |
$begingroup$
Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit.
Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges.
I already know that a graph is bipartit if they do not contain a cycle with an odd number of nodes.
I am also aware that it is possible to decide whether a graph contains a circle and whether it has odd number of nodes in linear time using Depth-First Search.
The problem is that this only findes a cycle and not all.
Is this approach even right and if yes how do I need to adapt it and if not what would be a better approach?
graph-theory bipartite-graph
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
$endgroup$
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
1
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22
add a comment |
$begingroup$
Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit.
Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges.
I already know that a graph is bipartit if they do not contain a cycle with an odd number of nodes.
I am also aware that it is possible to decide whether a graph contains a circle and whether it has odd number of nodes in linear time using Depth-First Search.
The problem is that this only findes a cycle and not all.
Is this approach even right and if yes how do I need to adapt it and if not what would be a better approach?
graph-theory bipartite-graph
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
$endgroup$
Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit.
Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges.
I already know that a graph is bipartit if they do not contain a cycle with an odd number of nodes.
I am also aware that it is possible to decide whether a graph contains a circle and whether it has odd number of nodes in linear time using Depth-First Search.
The problem is that this only findes a cycle and not all.
Is this approach even right and if yes how do I need to adapt it and if not what would be a better approach?
graph-theory bipartite-graph
graph-theory bipartite-graph
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
edited Dec 16 '18 at 19:37
Andrei
13.1k21230
13.1k21230
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
asked Dec 16 '18 at 19:20
Ymi_YugyYmi_Yugy
204
204
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
1
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22
add a comment |
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
1
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
1
1
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G setminus F$ is bipartite.
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.
[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
answered Dec 16 '18 at 19:41
MikeMike
4,396412
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043032%2ffind-an-edge-subset-such-that-the-graph-is-bipartite%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G setminus F$ is bipartite.
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.
[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
answered Dec 16 '18 at 19:41
MikeMike
4,396412
$endgroup$
add a comment |
$begingroup$
Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G setminus F$ is bipartite.
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.
[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
answered Dec 16 '18 at 19:41
MikeMike
4,396412
$endgroup$
add a comment |
$begingroup$
Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G setminus F$ is bipartite.
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.
[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
answered Dec 16 '18 at 19:41
MikeMike
4,396412
$endgroup$
Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G setminus F$ is bipartite.
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.
[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
answered Dec 16 '18 at 19:41
MikeMike
4,396412
edited Dec 16 '18 at 19:54
answered Dec 16 '18 at 19:41
MikeMike
4,396412
answered Dec 16 '18 at 19:41
MikeMike
4,396412
answered Dec 16 '18 at 19:41
MikeMike
4,396412
4,396412
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043032%2ffind-an-edge-subset-such-that-the-graph-is-bipartite%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Minimal or minimum? It may sound that I am splitting hairs but I am not. A set $F$ is minimal if (here) $G setminus F$ is bipartite but $G setminus F'$ is not for all proper subsets of $F$, a set $F$ is minimum if $G setminus F$ is bipartite and $G setminus F'$ is not for all $F'$ satisfying $|F'| < |F|$. A minimum set is minimal, but a minimal set is not necessarily minimum. [You did write minimal and I just want to make sure--finding a minimal set is in general easier than finding a minimum set]
$endgroup$
– Mike
Dec 16 '18 at 19:31
1
$begingroup$
I should have been more clear. I meant minimal. So there does not exist $F'subset{}F$ that satisfies the condition.
$endgroup$
– Ymi_Yugy
Dec 16 '18 at 19:55
$begingroup$
Good, I suspected that but I wanted to make sure :)
$endgroup$
– Mike
Dec 17 '18 at 3:22