Finding largest clique containing certain vertex
I want to find the largest clique containing certain vertex in a connected graph. In the wiki it said a maximal clique can be found by greedy search. However, this can't ensure that you find the largest clique IMO. For example,
If I want to find the largest clique containing A, and I do this by greedy search, I may end up finding (A,B), which is smaller than another clique (A,C,D).
I came up with a naive way to avoid smaller cliques: First find all vertices that are adjacent to your starting point, and then for each of these vertices (let's call it x), calculate how many other vertices that x is not adjacent to. After this, delete the vertex that is not adjacent to most number of vertices, and check if the rest of them form a clique. If not, repeat the procedure until the rest of them form a clique.
I understand this is a silly question but I'd appreciate it very much if anyone can tell me whether this approach is correct or not.
Enumerate all maximal cliques within your graph, then just check - do they contain given vertex or do not.
Maximal clique enumeration is NP-hard problem, that is, we don't know an efficient way to solve it at the moment. I have tried MACE (MAximal Clique Enumerater, ver. 2.2 and it worked quite well for me (it worked on graphs with thousands of vertices). You can check the details in corresponding article.
EDIT If you just want to check does the maximum clique contain a vertex or not, you can try cliquer to find the maximum clique.
- Using Extensions with Selenium (Python)
- How to calculate rolling / moving average using python + NumPy / SciPy?
- Can Anaconda be used to create virtual environments for Go?
- Selenium won't work unless I actually look at the Web page (perhaps anti-crawler mechanism by JavaScript?)
- Getting a weird error when trying to run xgboost.predict or xgboost.score
- How do you use input function along with def function?
- How to find if a signal is connected to anything
- Flatten an irregular (arbitrarily nested) list of lists
- Python Turtle Graphics : Created class error when using goto
- How to create a subclass in python that is inherited from turtle Module
- How to reorder columns if the columns have the same part name
- Turtle onkey() doesn't work despite all I've tried
- Python using turtle button
- How can I create a button in turtle?
- Python 3 Turtle - Hold 2 keys
- How do I properly support STARTTLS with aiosmtpd?
- How to import an existing requirements.txt into a Poetry project?
- Adding leading zero with regular expression
- Download files from Google Drive using Python and service account
- Extracting Owner’s Username from Nested Page on HuggingFace
- Django long request timeout
- exe file made with pyinstaller being reported as a virus threat by windows defender
- (Python) cant access attribute of an object unless I check nullity, why?
- How to set the timezone in Django
- Time different methods to recurse through directories in Linux
- How do you fix "Missing module docstringpylint(missing-module-docstring)"
- Underscore vs Double underscore with variables and methods
- FastAPI runs api-calls in serial instead of parallel fashion
- Project file window is yellow in PyCharm
- Performance results differ between run_in_threadpool() and run_in_executor() in FastAPI