A fake set covering problem?
$begingroup$
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be an undirected bipartite graph, $ forall u in L$, let $S:={(u,w_i)in E|w_i in R}$(The set of edges incident to $u$).
The problem is to find a minimum set $Ksubset L$ covering all $R$.
To clarify what I mean by covering: all vertices of $R$ should should have at least one edge connected to some $u in K$.
My intuition is that it's not $NP-Hard$. But can not find a polynomial time algorithm. Such that:
Each vertex from $L$ could cover multi-vertices of $R$.
The vertex from $L$ which has maximum edges toward $R$ will be selected first
Each vertex of $R$ is connected with at least one vertex of $L$
Edit: Here is an example, consider the following bipartite graph: $G={Lcup R,E}$, $L={1,2,3,4,5,6}$, $R={A,B,C,D}$ , $E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}$
And here is a covering minimum set will be ${2,4}$.
I have read many algorithms and solutions like maximum matching, complete matching, stable marriage, set cover problem, vertex cover in hypergraphs ...etc. Unfortunately no one match my case.
So i am here asking your help guys cause i about to fed up!!! SOS!!
This question was poted in
Minimum vertices set bipartite graph covering-special case
The greedy algorithm to approximate solve it is as follows:
1. Chose a vertex $a$ from $L$ which covers "more" nodes left in $R$ (i.e the vertex from $L$ with more edges)
1.1 Add the vertex $a$ the mininum cover set
1.2 Remove all the nodes in $R$ having an edge to $a$
1.3 Remove the vertex $a$ from $L$
2 In case $R$ is not empty, go to point 1
However, this is not the optimal one. Can any one help me?
graph-theory
edited Dec 4 '18 at 23:50
nafhgood
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
$endgroup$
add a comment |
$begingroup$
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be an undirected bipartite graph, $ forall u in L$, let $S:={(u,w_i)in E|w_i in R}$(The set of edges incident to $u$).
The problem is to find a minimum set $Ksubset L$ covering all $R$.
To clarify what I mean by covering: all vertices of $R$ should should have at least one edge connected to some $u in K$.
My intuition is that it's not $NP-Hard$. But can not find a polynomial time algorithm. Such that:
Each vertex from $L$ could cover multi-vertices of $R$.
The vertex from $L$ which has maximum edges toward $R$ will be selected first
Each vertex of $R$ is connected with at least one vertex of $L$
Edit: Here is an example, consider the following bipartite graph: $G={Lcup R,E}$, $L={1,2,3,4,5,6}$, $R={A,B,C,D}$ , $E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}$
And here is a covering minimum set will be ${2,4}$.
I have read many algorithms and solutions like maximum matching, complete matching, stable marriage, set cover problem, vertex cover in hypergraphs ...etc. Unfortunately no one match my case.
So i am here asking your help guys cause i about to fed up!!! SOS!!
This question was poted in
Minimum vertices set bipartite graph covering-special case
The greedy algorithm to approximate solve it is as follows:
1. Chose a vertex $a$ from $L$ which covers "more" nodes left in $R$ (i.e the vertex from $L$ with more edges)
1.1 Add the vertex $a$ the mininum cover set
1.2 Remove all the nodes in $R$ having an edge to $a$
1.3 Remove the vertex $a$ from $L$
2 In case $R$ is not empty, go to point 1
However, this is not the optimal one. Can any one help me?
graph-theory
edited Dec 4 '18 at 23:50
nafhgood
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
$endgroup$
1
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
1
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16
add a comment |
$begingroup$
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be an undirected bipartite graph, $ forall u in L$, let $S:={(u,w_i)in E|w_i in R}$(The set of edges incident to $u$).
The problem is to find a minimum set $Ksubset L$ covering all $R$.
To clarify what I mean by covering: all vertices of $R$ should should have at least one edge connected to some $u in K$.
My intuition is that it's not $NP-Hard$. But can not find a polynomial time algorithm. Such that:
Each vertex from $L$ could cover multi-vertices of $R$.
The vertex from $L$ which has maximum edges toward $R$ will be selected first
Each vertex of $R$ is connected with at least one vertex of $L$
Edit: Here is an example, consider the following bipartite graph: $G={Lcup R,E}$, $L={1,2,3,4,5,6}$, $R={A,B,C,D}$ , $E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}$
And here is a covering minimum set will be ${2,4}$.
I have read many algorithms and solutions like maximum matching, complete matching, stable marriage, set cover problem, vertex cover in hypergraphs ...etc. Unfortunately no one match my case.
So i am here asking your help guys cause i about to fed up!!! SOS!!
This question was poted in
Minimum vertices set bipartite graph covering-special case
The greedy algorithm to approximate solve it is as follows:
1. Chose a vertex $a$ from $L$ which covers "more" nodes left in $R$ (i.e the vertex from $L$ with more edges)
1.1 Add the vertex $a$ the mininum cover set
1.2 Remove all the nodes in $R$ having an edge to $a$
1.3 Remove the vertex $a$ from $L$
2 In case $R$ is not empty, go to point 1
However, this is not the optimal one. Can any one help me?
graph-theory
edited Dec 4 '18 at 23:50
nafhgood
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
$endgroup$
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be an undirected bipartite graph, $ forall u in L$, let $S:={(u,w_i)in E|w_i in R}$(The set of edges incident to $u$).
The problem is to find a minimum set $Ksubset L$ covering all $R$.
To clarify what I mean by covering: all vertices of $R$ should should have at least one edge connected to some $u in K$.
My intuition is that it's not $NP-Hard$. But can not find a polynomial time algorithm. Such that:
Each vertex from $L$ could cover multi-vertices of $R$.
The vertex from $L$ which has maximum edges toward $R$ will be selected first
Each vertex of $R$ is connected with at least one vertex of $L$
Edit: Here is an example, consider the following bipartite graph: $G={Lcup R,E}$, $L={1,2,3,4,5,6}$, $R={A,B,C,D}$ , $E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}$
And here is a covering minimum set will be ${2,4}$.
I have read many algorithms and solutions like maximum matching, complete matching, stable marriage, set cover problem, vertex cover in hypergraphs ...etc. Unfortunately no one match my case.
So i am here asking your help guys cause i about to fed up!!! SOS!!
This question was poted in
Minimum vertices set bipartite graph covering-special case
The greedy algorithm to approximate solve it is as follows:
1. Chose a vertex $a$ from $L$ which covers "more" nodes left in $R$ (i.e the vertex from $L$ with more edges)
1.1 Add the vertex $a$ the mininum cover set
1.2 Remove all the nodes in $R$ having an edge to $a$
1.3 Remove the vertex $a$ from $L$
2 In case $R$ is not empty, go to point 1
However, this is not the optimal one. Can any one help me?
graph-theory
graph-theory
edited Dec 4 '18 at 23:50
nafhgood
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
edited Dec 4 '18 at 23:50
nafhgood
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
edited Dec 4 '18 at 23:50
nafhgood
1,797422
edited Dec 4 '18 at 23:50
nafhgood
1,797422
edited Dec 4 '18 at 23:50
nafhgood
1,797422
1,797422
asked Dec 4 '18 at 14:24
capguyacapguya
61
asked Dec 4 '18 at 14:24
capguyacapguya
61
asked Dec 4 '18 at 14:24
capguyacapguya
61
61
1
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
1
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16
add a comment |
1
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
1
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16
1
1
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
1
1
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16
add a comment |
0
active
oldest
votes
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%2f3025647%2fa-fake-set-covering-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3025647%2fa-fake-set-covering-problem%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
1
$begingroup$
Welcome to MSE. Please use MathJax to format your equations.
$endgroup$
– Brahadeesh
Dec 4 '18 at 14:59
1
$begingroup$
As stated in the answer to the question you linked to, this is exactly the same problem as the set cover problem.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 15:45
$begingroup$
It seems that you didn't use $S$ anywhere after you defined it.
$endgroup$
– nafhgood
Dec 4 '18 at 23:16